Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

I'm really confused about the answer here, from the part that : Each of these edges creates a cycle of length between 3 and |V(cj)| when joined with T....

thank you !!


Let $T$ be any BFS spanning forest of $G$. Then $T$ has $\leq$ $n-1$ edges, and so there are $\geq n-2$ edges in $G \setminus T$, and so there are $|G \setminus T| \geq n-2$ cycles in $G$ that have exactly one edge in $G \setminus T$ (do you see why). The length of these cycles takes on values between $3$ and $n$ (so at most $n-2$ distinct values).

If $T$ is not a path $x_1\ldots x_n$ with the edge $x_1x_n \in G \setminus T$ then there will be no cycles $C$ with exactly one edge in $G \setminus T$ that have length exactly $n$, and so in this case there would be $G \setminus T \geq n-2$ cycles that have exactly one edge in $G \setminus T$ taking on values between $3$ and $n-1$ (so in this case at most only $n-3$ distinct values). Thus in this case we would be done (why).

So now we assume the remaining case: $T = x_1\ldots x_n$ and $x_1x_n$ is in $G \setminus T$, and use this to find an additional; cycle and then we would be done (why).

Let $x_ix_j$ be any other edge in $G \setminus T$, $j \geq i+2$; either $i \not =1$ or $j \not = n$ such an edge exists by the fact that $G$ is simple and has $2n-3$ $\geq (n-1) + 2$ edges. If $i \not = 1$ and $j \not =1$ then $x_1x_2\ldots x_ix_jx_{j+1}\ldots x_nx_1$ is a cycle that contains 2 edges in $G \setminus T$ (namely $x_ix_j$ and $x_1x_n$. If $i=1$ then $x_1x_jx_{j+1}\ldots x_nx_1$ is a cycle that contains 2 edges in $G \setminus T$ (namely $x_1x_j$ and $x_1x_n$). The case where $j=n$ can be handled analagously (check this to see for yourself). In any case we indeed found an additional cycle and thus per the previous paragraph we are done.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.