Proof Involving Graph Connectivity

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?

• 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

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$

• 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. – vrume21 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.)

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.