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.

I have the following proof: let $G$ be a graph with $n$ vertices and $n-1$ edges, prove that $G$ is connected iff $G$ has no cycles.

I proceed proving "only if" first. Assume $G$ has some cycle consuming $|C| \le n$ vertices and $|C|$ edges. We are thus left to try and connect $n-|C|$ vertices and $n-1-|C|$ edges. This subgraph must contain at least $|C|+1$ connected components and because $|C| \gt 0$, $|C|+1 \gt 1$, therefore G cannot be connected.

Now proving that if $G$ has no cycles, then it is connected. Because $G$ has $n \epsilon N, n \gt 0$ vertices, we can walk along them, connecting them. Take $v \epsilon V, v={v_1, ..., v_n}$ where $|v|=n$. Then first connect $v_1$ and $v_2$, consuming one edge. Then connect $v_2$ and $v_3$ consuming another edge. Proceed this way until $v_{n-1}$ and $v_n$ are connected, after which point, $n-1$ edges will have been consumed. $v$ clearly has no cycles and is connected.

Does this proof look correct?

share|improve this question
    
Why must the subgraph have at least $|C|+1$ components? I'm not too sure I follow the first part. –  EuYu Sep 13 '13 at 18:19

3 Answers 3

up vote 1 down vote accepted

The first part is ok, the second could be improved.

The problem lies that you need to prove this for any graph and any set of edges, while you suggest that you add edges as you wish (by walking those vertices). You could make this into a proper proof, but I suggest the another approach, namely assume that graph is not connected, it has $n-1$ edges and prove that it has a cycle (there are at least two connected components, and one of them has size $k$ and at least $k$ edges, hence it has a cycle).

I hope this helps $\ddot\smile$

share|improve this answer
    
I agree your suggestion sounds better for the second part, but could you elaborate on how I could turn the argument as is into a proper proof? You don't need to refer to the problem I gave, you could really give any example you want. I would just like to see how this argument is implemented. –  bam54 Sep 18 '13 at 23:28

This comes almost straight from one of my old notebooks. Maybe it will help. I think we are trying to make the same argument.

$\textbf{Theorem:}$ Let $G$ be a graph with $n$ vertices and $n-1$ edges. $G$ is connected if and only if $G$ contains no cycles.

$\textbf{Proof:}$ Let $G$ be a connected graph with $n$ vertices and $n-1$ edges. Suppose $G$ contains a cycle $C$ with edge $e$. Then $G-e$ is connected with $n$ vertices and $n-2$ edges. But a connected graph with $n$ vertices must have at least $n-1$ edges, and so this is impossible. Therefore $G$ is acyclic.

Conversely, let $G$ be an acyclic graph with $n$ vertices and $n-1$ edges. Let $V_1, V_2, ...,V_k$ be the components of $G$ where each $V_i$ has $n_i$ vertices ($1 \leq i \leq k$). Since each graph $V_i$ is acyclic, each graph $V_i$ has $n_i-1$ edges. Hence $$ n-1=\sum_{i=1}^k(n_i-1)=n-k \Rightarrow k=1. $$ Thus $G$ is connected, and the theorem follows.

(refinements are always encouraged.)

share|improve this answer

A little topology goes a long way. The following answer uses the spirit of topology, but still restricts to the elementary tools of finite graph theory.

The Euler characteristic $\chi(G)$ of a finite graph $G = (V,E)$ is defined to be $\# V - \# E$. If the connected components of $G$ are $G_1,\ldots,G_c$, then $\chi(G) = \sum_{i=1}^n \chi(G_c)$.

Lemma: For a connected finite graph $G$, $\chi(G) \leq 1$, with equality iff $G$ is a tree.

Proof: Since every finite tree with more than one vertex has a degree one vertex, an easy "pruning" argument shows by induction that every finite tree has $\chi(G) = 1$. Conversely, if $G$ is connected and is not a tree, we may remove a positive number of edges in order to get a tree, so $\chi(G) < 1$.

Now let $c$ be the number of components. By hypothesis

$1 = \chi(G) = \sum_{i=1}^c \chi(G_i)$.

If $c = 1$, then by the Lemma $G = G_1$ is a tree. If $c > 1$ then for some $i$ we must have $\chi(G_i) < 1$, and thus at least one component has a cycle.

share|improve this answer

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.