Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thank you for your time! –  passenger Feb 28 '12 at 20:47
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.