2
$\begingroup$

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?

$\endgroup$
2
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I don't see how to continue from your last point. What is the implication of starting from a spanning tree containing a vertex of degree 3? What argument can I make based on your earlier notes? $\endgroup$
    – Sandstar
    Mar 8 '20 at 13:04
  • $\begingroup$ @Sandstar The point is that any set of edges that doesn't contain a cycle can be extended to a spanning tree. So if you start from three edges with a common vertex, the spanning tree you get must have a vertex which meets more than two edges, so can't be a path. $\endgroup$ Mar 8 '20 at 14:40

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.