We have a connected graph $G(V,E)$ that has $|E|= n$ edges and $n$ vertices.
Prove that the graph has one cycle in it.
I'm little bit confused here. I tried some ways but failed. Can you direct me?
[Math] Prove that a graph with the same number of edges and vertices contains one cycle
graph theory
Best Answer
$G$ is connected so it has a spanning tree $T$. This uses up $n-1$ edges and has no cycles. There is one edge $e$ not used in the tree, say $e=(u,v)$. So any cycle in $G$ would have to use $e$.
Now in $T$ there is a unique path between vertices $u$ and $v$ and so in $T\cup e$ that path plus $e$ is one cycle, say $C_1$. Can there be any others? Suppose $C_2$ is another cycle, and so we know that it must use $e$ but $C_2\neq C_1$. Then $C_2\setminus e$ and $C_1\setminus e$ are two different paths in $T$ from $u$ to $v$, a contradiction.