# Prove that every connected undirected graph with n vertices has at least n-1 edges.

I would appreciate it if anyone can verify my proof. It is a proof by induction, but I attempt to reason things out rather than using a purely mathematical approach, in a similar vein to many other graph theory proofs I have come across.

Base case: A graph with 1 vertex is defined to be connected. Clearly it has at least 0 edges.

Inductive case: Assume that for some $k \in \mathbb Z^+$, every connected undirected graph with $k$ vertices has at least $k-1$ edges. If we select any of such a graph, and introduce a single vertex $k'$, then there are now $k+1$ vertices. We know that there was a path between every two distinct vertices in the old graph. To maintain connectivity, we must join this new vertex $k'$ to $at$ $least$ $one$ of the $k$ vertices in the old graph. Suppose we join $k'$ to a vertex $v$ in the old graph. Then there will be a path from $k'$ to each of the $k$ vertices in the old graph $via$ $v$. Thus the new graph is connected, and it has $k+1$ vertices and $k$ edges.

Therefore $\forall$ $n\in\mathbb Z^+$, every connected undirected graph with $n$ vertices has at least $n-1$ edges.

• Seems to be correct !! Nov 21 '14 at 8:53
• Thanks! I'll wait for a couple more responses so that I can be certain that my proof is valid. Nov 21 '14 at 8:56
• Try to write little crisper and compact !! Nov 21 '14 at 8:59
• As I am a beginner to graph theory, I find that writing proofs in a verbose manner aids me greatly in my understanding of the topic. But thanks for your suggestion :) Nov 21 '14 at 9:02
• the only thing I would change is that since we join $k'$ to at least one of the vertices in the old, notice that we might make it adjacent still to more than one of the old vertices. So, the conclusion will be "the new graph is connected, and it has k+1 vertices and at least k edges." The graph might well have more than $k$ edges since $k'$ might have been adjacent to several, and also since the smaller graph might have had more than $k-1$ edges to begin with, but that is okay. Nov 21 '14 at 9:12

I'm sorry, but your proof is incomplete; you fell into the so-called "induction trap".

For the induction step, you assume that any connected graph with $k$ vertices has at least $k-1$ edges; and you want to prove that any connected graph $G$ with $k+1$ vertices has at least $k$ edges. In trying to prove this, you assume that $G$ was obtained by adding a new vertex (which you confusingly call $k'$) to a connected graph with $k$ vertices. But you have not justified this assumption.

To justify your argument, you would have to show that every connected graph with $k+1$ vertices can be obtained by adding a vertex (and some edges) to some connected graph with $k$ vertices. In other words, you have to show that, given any connected graph with $k+1$ vertices, you can find a vertex whose deletion results in a connected graph. This is true, but requires a proof. (Well, it's true for finite graphs, which is what we're talking about. In a connected infinite graph, it's possible that deleting any vertex disconnects it.)

For an alternative approach, you can delete an arbitrary vertex $v$ from a $k$-vertex graph $G$, without worrying about whether $G-v$ is connected or not; you then apply the induction hypothesis to each connected component of $G-v$, however many there may be. In this approach, you have to use the style of induction where you prove the statement for $k$ assuming that it holds for all numbers smaller than $k$.

• Thanks for pointing out my error! I had a feeling I was doing something wrong. For your second paragraph, did you instead mean "you would have to show that every connected graph with k+1 vertices can be obtained by adding a vertex (and some edges) to some connected graph with k vertices"? Nov 21 '14 at 9:26
• Thanks for pointing out my error. Corrected.
– bof
Nov 21 '14 at 9:28
• Very good observation. I found many proof online implicitly assume the fact that any connected graph with $n$ vertices must be obtained from adding one vertex to some connected graph with $n-1$ vertices. This fact is equivalent to say for any connected graph, there always exist a vertex such that if we remove this vertex and all edges incident to it, the remaining graph is still connected. These facts must be proved and cannot be treated as trivial thing. Jan 27 at 7:54