3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Seems to be correct !! $\endgroup$ – Hirak Nov 21 '14 at 8:53
  • $\begingroup$ Thanks! I'll wait for a couple more responses so that I can be certain that my proof is valid. $\endgroup$ – Vizuna Nov 21 '14 at 8:56
  • $\begingroup$ Try to write little crisper and compact !! $\endgroup$ – Hirak Nov 21 '14 at 8:59
  • $\begingroup$ 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 :) $\endgroup$ – Vizuna Nov 21 '14 at 9:02
  • $\begingroup$ 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. $\endgroup$ – JMoravitz Nov 21 '14 at 9:12
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Vizuna Nov 21 '14 at 9:26
  • $\begingroup$ Thanks for pointing out my error. Corrected. $\endgroup$ – bof Nov 21 '14 at 9:28

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.