2
$\begingroup$

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question

Prove, by induction on k, that a connected component of k nodes has at least k − 1 edges.

Any suggestions? Thanks in advance

1 Answers 1

1

Outline of Proof: Let $G$ be a connected graph with $k$ vertices. If every vertex of $G$ has at least two edges, then the number of edges must be at least $k$.

If not every vertex of $G$ has two or more edges, let $v$ be a vertex that has only one edge. Remove $v$, and $v$'s single edge. The remaining graph $G'$ is connected, has $k-1$ vertices, and therefore by the induction hypothesis has at least $k-2$ edges. Put our vertex $v$ back, and its edge. That gets us to at least $k-1$ edges.

  • 0
    Usual induction proof. Result is true for $0$ vertices (or $1$ if you prefer). We show if it is rue for any connected graph with $k-1$ vertices, it is true for any connected graph with $k$ vertices. (If you prefer going $k$ to $k+1$, need minor changes in my answer.) There are two cases: (i) Every vertex has $\ge 2$ edges. Then we don't even care about connectedness, the usual every edge has $2$ vertices gives us a count of $\ge k$. (ii) there is a vertex with $1$ edge. Do argument as I did. You will have to **prove** that the graph obtained by deleting the vertex, edge is still connected.2012-12-02