0
$\begingroup$

Let $G=(V,E)$ a graph. Prove that $G$ has no cycles if and only if $G$ has $n-m$ connected components where $n$ is the number of vertices of $G$ and $m$ is the number of edges of $G$.

The thing I did is that since $G$ has no cycles then $ \frac{m}{n} <1$.

Can someone give me some hints-ideas?

Thank's in advance!

2 Answers 2

4

A tree is a connected graph with $n - 1$ edges. If you take any edge away from a tree, the number of components increases. If you add any edge to a tree, a cycle is created. So, your situation is a forest of $n - m$ trees, i.e., $n - m$ connected components, each of which is a tree. If you take away any edge, it creates more connected components. If you add any edge, it adds a cycle. This is an intuitive way to think of it. Here's an actual proof.

Proof: Assume $G$ has no cycles. Then each connected component has number of vertices in that component - 1 edges, as each component is a tree. Adding up the edges over the various components, if there are $k$ components, gives $n - k$ edges. Since the number of edges is $m$, we have $n - k = m$, or $k = n - m$. This is what we wanted to show.

Now, assume $G$ has $n - m$ connected components. Each component must at least have number of vertices in the component - 1 edges. And, if we have exactly that many edges per component, we have exactly $n - (n - m) = m$ edges. Thus, each component is a tree. So each component has no cycles. Or, another way to think of this, if one component had more than that number of edges, we'd end up with more than $m$ edges, which would contradict the fact that we have $m$ edges.

1

Add to the statement the claim that the graph has at least $n-m$ connected compenents (regardless of whether it has cycles); then for any $n$ one can apply induction on $m$. For $m=0$ the graph never has cycles and always has exactly $n$ connected components, so the base case is OK. Now let the graph have $m>1$ edges, and pick any edge $e$, let G' be the result of removing $e$ from $G$, which clearly does not have fewer connected components than $G$ has.

First suppose G' has as many connected components as $G$. Then the two vertices at the ends of $e$ are connected in G', and so $G$ has a cycle; also the number of connected components is at least $n-(m-1)$ by the induction hypothesis applied to G'. So both parts of the equivalence to be proved are false in this case; moreover $G$ has strictly more than $n-m$ cycles.

Now suppose G' has more connected components than $G$. This can only be because the connected componenent containing $e$ in $G$ has become two connected components in G'; therefore G' has exactly one more connected component than $G$ has. Also $e$ does not occur in a cycle in $G$, so $G$ is without cycles if and only if G' is. The hypothesis applied to G' now gives the equivalence sought for $G$, and $G$ has at least $n-(m-1)-1=n-m$ connected components.