Graph has at least 2 cycles of equal length if e(G)=2v(G)-3

389 Views Asked by At

As the title says, I am trying to show that if a graph $G$ is such that $v(G)\geq4$ and the number of edges it has is 3 less than twice the number of vertices, i.e. that $$ e(G) = 2v(G) - 3, $$ then the graph has at least 2 cycles of equal length.

Progress:

Clearly in order to be a cycle we need at least 3 vertices, so the possible cycle lengths are $$ 3,4,5, ... , v(G). $$ Now the minimum spanning tree $T$ is a tree and therefore its number of edges is $e(T) = v(G) - 1$, and so by adding edges to get to $G$ we find that there are $v(G)-2$ edges to add. And since this was a tree each new edge will create a cycle.

So we can assume that each additional edge creates a cycle with a distinct number of vertices, using all $v(G)-2$ possibilities.

Now I obviously should find a contradiction somewhere, but I'm not sure exactly how. Any help?

1

There are 1 best solutions below

2
On BEST ANSWER

This isn't true for $v(G)=3$, so I will assume $v(G)\geq 4$.

It is actually possible that all the cycles you create by adding individual edges to the spanning tree (that is, the fundamental cycles for this spanning tree) have distinct lengths. However, the only way this can occur is if your original spanning tree is a path of length $v(G)-1$, since you would need to have a cycle of length $v(G)$ using the edges of the spanning tree and one other edge.

Remember that you can choose any spanning tree at the start. So all you need to do is show that there exists a spanning tree which isn't a path - then you choose that spanning tree and the situation above can't happen. You can show that there is a vertex in $G$ of degree at least $3$ (assuming $v(G)\geq 4$), and then take a spanning tree including any three edges meeting that vertex; this can't be a path.