6
$\begingroup$

For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42)

I am trying to prove the above claim. So far I have reasoned as follows:

  • G must be connected because $2n-3\ge n-1$ for $n\ge4$, and any simple n-vertex graph with at least $n-1$ edges must be connected.

  • Let T be a spanning tree of G. T must have $n-1$ edges. Therefore T has at least $2n-3 - (n-1) = n-2$ fewer edges than G. That is, $|e(G) \setminus e(T)| \ge n-2$.

  • Each one of these 'extra' edges adds exactly cycle to G, so G has at least $n-1$ cycles, each with length 3 to n.

  • Because there are at least n-2 cycles in G, it suffices to show that $n-2$ of these edges cannot all have distinct sizes. (I'm unsure about this line... is this a correct statement?)

From here I've lost my way, but I think I am on the right track. For what it's worth, this question appears right after the section that introduces trees, spanning trees, and their properties etc.

Thank you!

$\endgroup$
  • 2
    $\begingroup$ The claim that a simple graph of order $n$ and at least $n-1$ edges iimplies that $G$ is connected is wrong. $\endgroup$ – Jernej Mar 3 '14 at 19:55
4
$\begingroup$

Jernej is correct, $|V(G)| = n$ and $|E(G)|=2n-3$ does not imply that $G$ is connected. Counter example: Consider $n = 6$, then $2n-3=9$. You can construct a graph consisting of a single isolated node and an almost completely connected component with 5 vertices. This is possible because $|E(K_5)| = 10 > 9$.

WLOG let $G$ have $k$ connected components $c_i$, $i=1,\dots,k$. Let $c_j$ be such that $|V(c_j)| \geq 4$ and $|E(c_j)| \geq 2\cdot|V(c_j)| - 3$. Such a $c_j$ must exist because $G$ could not have $2n-3$ edges otherwise. Now consider $T$, the spanning tree of $c_j$. It consists of $|V(c_j)| - 1$ edges, so there are at least $|V(c_j)| - 2$ edges left. Each of these edges creates a cycle of length between 3 and $|V(c_j)|$ when joined with $T$. Since there are $|V(c_j)| - 2$ edges and $|V(c_j)| - 2$ possible distinct cycle lengths this is not yet enough to apply the pigeon hole principle. However, observe that when there is a cycle of length $|V(c_j)|$ every additional edge will create at least two new cycles. Hence either there will be a repeated cycle length when choosing $|V(c_j)|-2$ lengths with $|V(c_j)|-2$ edges, or if not, then there must be a cycle of length $|V(c_j)|$ and so there will be $2(|V(c_j)|-3)+1$ cycles. $2(|V(c_j)|-3)+1$ > $|V(c_j)|-2$ for all $|V(c_j)| > 3$ so the pigeon hole principle can be applied in this case. $\quad\square$

$\endgroup$
  • $\begingroup$ Thank you. I had just come back because I had realized that my solution was incorrect. Very thorough explaination! $\endgroup$ – mb7744 Mar 17 '14 at 23:45
2
$\begingroup$

You are almost done. There are at least $n-1$ cycles, each of them has a size from 3 to $n$ ($n-2$ possibilities) so at least two of them have the same size (pigeonhole principle).

$\endgroup$

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.