# Graph Theory and Induction

A simple undirected graph is connected if there is a path between every pair of vertices in the graph. Prove: if H is an undirected simple connected graph with n vertices, then H has ≥ n − 1 edges. Use induction.

Teacher has a knack for giving practice problems that combine multiple concepts. I am at a complete loss as to how to even begin using induction to prove the above problem. Any help would be appreciated!

• show it holds for one vertex or a pair of two and then use induction to prove if it holds for n, it holds for n+1, the rest follows. – user451844 Aug 1 '17 at 1:48
• @RoddyMacPhee I could be wrong but I think the OP already knows what a proof by induction is, and is asking how to prove "if it holds for n, it holds for n+1". – bof Aug 1 '17 at 2:58

Does the result hold for 2 vertices? Ask yourself, how many edges does a connected graph with 2 vertices have? Is it at least $n-1=2-1=1$?

Now, suppose you got yourself a connected graph on $n$ vertices where $n>2$. Carefully remove a vertex which does not disconnect the graph (you must convince yourself, and the reader of your proof, that this is possible or use some theorem from your text/notes) say $G-v$ is connected. $G-v$ has one less vertex, so by induction it has at least $(n-1)-1$ edges. Add $v$ back in along with all those edges incident to $v$ (What's the smallest number of edges added back in at this step?). Now, count (get a lower bound) on the number of edges in $G$. Hopefully, the number of edges is at least $n-1$.

Proving the n=1 case is just giving an example so I'll leave that to you.

You can subdivide a graph into sub graphs with links between them. So if $H_{n+1}$ is a graph of n+1 nodes you can consider it as two graphs of $H_n$ and $H_1$. Since the graph is connected there must be at least one edge between $H_n$ and $H_1$.

So your inductive step is to assume that $H_n$ has at least (n-1) links. Then $H_{n+1}$ must have at an extra edge to join the subgraphs.

I think strong induction might be the best approach here, to avoid having to find a non-cut vertex (a vertex that, when removed along with its incident edges, does not disconnect the graph). Induction proofs require a family of propositions $P(n)$, indexed by natural numbers $n$. I usually find it easier to explicitly define it:

$P(n) :$ For all connected graph $G$ with $n$ vertices, $G$ has at least $n - 1$ edges.

We need to prove $P(1)$ first. That is, if $G$ is a connected graph with $1$ vertex, then $G$ has at least $0$ edges. This is clear of any graph, not just connected ones with $1$ vertex, so $P(1)$ is true.

We suppose now that, for a fixed $n > 1$, $P(k)$ is true for all $k < n$, and proceed to prove $P(n)$. We need to show that, given any connected $G$ graph with $n$ vertices, we have at least $n - 1$ edges, so let's suppose that we have some graph $G$ fitting these premises.

Take any vertex $v$ of $G$, delete it, along with all of its incident edges, to form a new graph $G'$. Note that $v$ cannot have zero degree, because then it would not be connected to the rest of the graph. We cannot assume $G'$ is connected (which would be handy, so that we could apply $P(n - 1)$), but what we can do is consider the connected components of $G'$. Let $G_1, G_2, \ldots, G_m$ be the number of connected components of $G$. For each $i = 1, \ldots, m$, let $n_i$ and $e_i$ be the number of vertices and edges respectively of $G_i$.

Note that $G'$ has $n - 1 = n_1 + \ldots + n_m$ vertices and $e_1 + \ldots + e_n$ edges. In particular, $n_i < n$ for all $i = 1, \ldots, m$. We can therefore use our induction hypothesis, and conclude that $P(n_i)$ is true for all $i$. That is, $e_i \ge n_i - 1$. Summing up, we get, $$n - 1 = n_1 + \ldots + n_m = (n_1 - 1) + \ldots + (n_m - 1) + m \le e_1 + \ldots + e_m + m$$ Since removing $v$ created $m$ connected components, it follows that $v$ must have had at least $m$ edges incident to it (at least one edge must have connected to each connected component of $G'$ to connect them all in $G$). Thus, if $e$ is the number of edges in $G$, we have $$n - 1 \le e_1 + \ldots + e_m + m \le e,$$ as required. Thus, by (strong) induction, $P(n)$ holds for all $n$.

• Yeah, considering the connected components is a nice way to get around the apparent difficulty of finding a non-cut vertex. – Paddling Ghost Aug 1 '17 at 2:57
• @PaddlingGhost I don't think it's all that difficult to prove that, if $d(u,v)$ is at a maximum, then $u$ and $v$ are non-cut vertices. – bof Aug 1 '17 at 3:08

This is not the sort of proof you're looking for (see the answer by Paddling Ghost for that) because it does not use induction.

Let $V(H)=\{v_0,v_1,v_2,\dots,v_{n-1}\}.$

For each $i\in\{1,2,\dots,n-1\},$ choose a vertex $w_i$ so that $v_iw_i$ is the first edge of a shortest path from $v_i$ to $v_0;$ in other words, $w_i$ is a neighbor of $v_i$ such that $d(w_i,v_0)\lt d(v_i,v_0).$

To finish the proof, show that the edges $v_iw_i\ (i=1,2,\dots,n-1)$ are distinct. (In other words, if going from $v_i$ to $v_j$ is the first step on a shortest path from $v_i$ to $v_0,$ then going from $v_j$ to $v_i$ can't be the first step on a shortest path from $v_j$ to $v_0.$)