Let k be the maximum length of a cycle in a nonseparable gra

Let k be the maximum length of a cycle in a nonseparable graph G. Prove that if C and C\' are any two k-cycles in G, then C and C\' have at least two vertices in common. Show that the result in (a) cannot be improved.

Solution

(a)I must prove that in a non-separable graph G, (non-separable: the removal of any vertex of G will result in a disconnected graph) let k= the maximum length of a cycle in G, and let C and C\' both be k-cycles. Then C and C\' have at least 2 vertices in common.

Now, I understand why this must be so. If there are no vertices, or one vertex in common then I either have that G is separable (a contradiction) or that there exists a cycle with length greater than k (a contradiction). However, If C and C\' have two vertices in common, let\'s call them U0 and V0, and let all the vertices of C be called Ui for all 1<=i<=k. and let the names of the vertices in C\' be Vj for all 1<=j<=k. then I construct the cycle U0 to U1 to U2 to U3 to U4 to ... to V0 to V1 to V2 to V3 ... to U0. then I have a cycle of length greater than k... thus we have a contradiction in every case where C and C\' have common vertices except in the case where C=C\'. The conclusion that I\'m reaching is that a cycle of maximum length in a non-separable graph G must be unique.

(b)

Theorem. If the graph G has a vertex v that is connected to a vertex of the component G1 of G, then v is also a vertex of G1.

Suppose there exists one and only edge connecting C to C\'. Removing this edge would yield two connected components.

Suppose there exists two edges connecting C to C\'. Removing one edge would yield one connected component. C and C\' have at least two vertices in common.