let $G$ be a simple $n$-vertex graph with at least $2n−3$ edges. Prove that $G$ has two cycles of equal length.

Question

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 !!

Answer 1

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.