5
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user451844 Aug 1 '17 at 1:48
  • $\begingroup$ @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". $\endgroup$ – bof Aug 1 '17 at 2:58
4
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Yeah, considering the connected components is a nice way to get around the apparent difficulty of finding a non-cut vertex. $\endgroup$ – Paddling Ghost Aug 1 '17 at 2:57
  • $\begingroup$ @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. $\endgroup$ – bof Aug 1 '17 at 3:08
1
$\begingroup$

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.$)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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