2
$\begingroup$

Claim: Every connected graph with $n$ vertices has at least $n - 1$ edges.

Proof by induction:

$P(n)$ = "Every connected graph with $n$ vertices has at least $n - 1$ edges." $\forall n \ge 1$

Base case: A graph with $1$ vertex has $0$ edges.

Inductive step:

  1. Remove a vertex with the lowest degree and all its edges from the connected graph with $n + 1$ vertices.

  2. The resulting graph has $n$ vertices. Apply the inductive hypothesis - this graph has at least $n - 1$ edges.

  3. When you add the removed vertex back, it must connect to at least $1$ vertex in order for the overall graph to be connected.

  4. The graph now contains at least $n - 1 + 1$ or $n$ edges

I'm new to graph theory, so I'm wondering if I completed this induction proof with the right steps. Any other methods or additions to this proof would also be appreciated. Thanks!

$\endgroup$
  • 1
    $\begingroup$ There is one problem with the argument: how do you know that the smaller graph is connected? $\endgroup$ – Brian M. Scott Oct 14 '16 at 15:00
2
$\begingroup$

HINT: You have to work just a little harder, because the graph that remains after you remove a vertex need not be connected. However, your argument can be repaired to take that into account. Remove any vertex $v$; it needn’t be one of minimal degree. The remaining graph has $n$ vertices.

Say that it has $m$ components, $C_1,\ldots,C_m$, and for $k=1,\ldots,m$ let $n_k$ be the number of vertices in $C_k$. By the induction hypothesis each $C_k$ has at least $n_k-1$ edges, so the whole remaining graph has at least

$$\sum_{k=1}^m(n_k-1)=n-m$$

edges. What’s the minimum number of edges that you could have removed along with $v$?

$\endgroup$
0
$\begingroup$

No, this doesn't quite work as written. You can't be sure that the graph that results from your step 1 is connected.

Hint. Prove this lemma:

Let $G$ be a connected graph with $m$ vertices. For every positive $n\le m$, there is a subgraph of $G$ that has $n$ vertices and $n−1$ edges.

by induction on $n$. Your goal then follows by setting $n=m$.

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