3
$\begingroup$

How would you prove that a graph $G = (V, E)$ that has no cycles and contains $|V| - 1$ edges must be a tree?

Definition used for a tree: $A$ graph is a tree if it is connected and has no cycles and a simple cycle is formed if any edge is added to $G$, but is not connected if any single edge is removed from $G$.

$\endgroup$
  • $\begingroup$ What definition of tree are you using? $\endgroup$ – Michael Biro Mar 24 '13 at 23:01
  • $\begingroup$ A graph is a tree if it is connected and has no cycles and a simple cycle is formed if any edge is added to G, but is not connected if any single edge is removed from G. But i can't figure out how it is related? $\endgroup$ – jack Mar 24 '13 at 23:04
7
$\begingroup$

Can you show that a graph with no cycles and $|V|-1$ edges must be connected?

Once you do that, show that adding an edge closes a cycle (since $G$ is connected, there is already a path connecting the two vertices). Then show that removing an edge disconnects the graph (as otherwise there would have been a cycle).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @MichealBiro is there a way to do this with induction? $\endgroup$ – jack Mar 25 '13 at 0:58
  • 1
    $\begingroup$ Sure, induction would work. Add an edge, then replace the given connected pair of vertices with a new vertex. We now have a smaller problem, and just need to show that we did not create any cycles. $\endgroup$ – Michael Biro Mar 25 '13 at 1:12
  • $\begingroup$ @MichealBiro I am not quite sure what you meant, how would you do that, I can get the base case and hypothesis statement, but i get stuck at the induction step how would you prove that a graph with K+1 edges is tree? $\endgroup$ – jack Mar 25 '13 at 18:54
  • 2
    $\begingroup$ Use induction on $|V|$. The base case is easy, so assume that any graph with $|V| < n$, no cycles and $|V| - 1$ edges is connected. Take any graph $G$ with $n$ vertices, no cycles and $n - 1$ edges. Pick an edge $e = (u,v)$ and condense $G$ by replacing vertices $u$ and $v$ with vertex $uv$, and replacing any edge $(u,x)$ or $(v,x)$ with $(uv,x)$. The resulting graph $G^\prime$ is still simple, has no cycles, and has $n-1$ vertices with $n-2$ edges, so by induction it is connected. We can easily convert paths in $G^\prime$ into paths in $G$, so $G$ is connected. $\endgroup$ – Michael Biro Mar 26 '13 at 6:45

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.