5
$\begingroup$

I've got this problem from a textbook and couldn't find out what the problem should be here.

Suppose we want to prove that if $G = (V,E)$ is a connected graph with $|V| = |E| + 1$, then it is a tree.

What is wrong with the following proof?

We already assume that the considered graph is connected, so all we need to prove is that it has no cycle. We proceed by induction on the number of vertices. For $|V| = 1$, we have a single vertex and no edge, and the statement holds.

So assume the implication holds for any graph $G = (V, E)$ on $n$ vertices. We want to prove it also for a graph $G' = (V', E')$ arising from $G$ by adding a new vertex. In order that the assumption $|V'| = |E'|+1$ holds for $G'$, we must also add one new edge, and because we assume $G'$ is connected, this new edge must connect the new vertex to some vertex in $V$. Hence the new vertex has degree $1$ and so it cannot be contained in a cycle. And because $G$ has no cycle (by the inductive hypothesis), we get that neither does $G'$ have a cycle, which finishes the induction step.

$\endgroup$
  • 2
    $\begingroup$ Can every connected graph with $|V|=|E|+1$ be obtained by adjoining an edge and vertex to a connected graph with $|V|=|E|+1$? $\endgroup$ – Servaes Jun 27 '19 at 22:25
  • $\begingroup$ Oh how could i missed that. Would the rest of the induction be right if the new graph G' would have |𝑉| + 1=|𝐸|+1+1 ? $\endgroup$ – Jag Jun 27 '19 at 22:32
  • $\begingroup$ I'm not saying it is false, I'm just saying it might not be so clear whether it is true. $\endgroup$ – Servaes Jun 27 '19 at 22:37
  • $\begingroup$ @Jag, Servaes's point is that you need to start with a graph $G$ that has $|V(G)|=|E(G)|+1$ and show it can be built from a smaller graph that has that same property. $\endgroup$ – Cheerful Parsnip Jun 28 '19 at 1:34
3
$\begingroup$

Suppose we change the statement we're trying to prove: replace "connected graph $G=(V,E)$ with $|V|=|E|+1$" with "graph $G=(V,E)$ with no isolated vertices amd $|V|=|E|+1$". (Also, to give us a nice basis for the induction, let's just consider graphs with at least $2$ vertices.)

The "proof" seems to work the same as before. The only place we used connectedness was when we said "because we assume $G'$ is connected, this new edge must connect the new vertex to some vertex in $V$." But we can just as well say "because we assume $G'$ has no isolated vertices, this new edge must connect the new vertex to some vertex in $V$."

But the modified statement is false: the graph $G=K_3+K_2$ has $4$ edges and $5$ vertices, has no isolated vertices, and is not a tree. So what went wrong??

In a proof by induction on the number of vertices, going from $n=4$ to $n=5$ means that we assume that the statement holds for every $4$-vertex graph, and we have to prove it for every $5$-vertex graph. Note that we tacitly assumed that every $5$-vertex graph which satisfies the hypotheses can be obtained by adding a vertex to some $4$-vertex graph which satisfies the hypotheses. For the modified statement this is false; the graph $G=K_3+K_2$ can not be obtained by adding a vertex to a graph with $4$ vertices and $3$ edges and no isolates.

Going back to the original statement, a connected graph with $5$ vertices and $4$ edges can be obtained by adding a vertex and an edge to a connected graph with $4$ vertices and $3$ edges (because it is a tree, so it has a leaf, and removing a leaf gets us the desired $4$-vertex graph), but that needs to be shown.

To repair the proof, we could say: Let $G$ be any connected graph with $n+1$ vertices and $n$ edges. Since $G$ has more vertices than edges, its average degree is less than two, so it has a vertex $v$ of degree less than two. The degree can't be zero (since $G$ is connected), so $v$ has degree one. Then the graph $G'=G-v$ has $n$ vertices and $n-1$ edges, and $G'$ is connected, because you can't disconnect a connected graph by removing a vertex of degree one.

$\endgroup$
1
$\begingroup$

Every proof of induction over a set $S$ explicitly assumes some recursive way of constructing every object in $S$. Your $S$ in your proof is the set of all connected graphs such that $|V| = |E| + 1$. Your recursive construction is to add a vertex+edge to an existing element. So your proof is assuming that this algorithm can construct all such elements of $S$.

  • How do you know that every $|E| = |V| + 1$ graph can be constructed that way?
  • The construction algorithm suggested, if you were to allow some leeway for intuition, would intuitively describe a way of constructing trees. So you are somewhat begging the question with this approach.

An alternative approach is to use your idea, but instead first use it to show inductively the converse: that every tree has $|E| = |V| + 1$. Then assert (or prove somehow, but assert is probably enough) that every connected non-tree graph can be constructed by adding edges to a tree (with the same number of vertices), so $|E| > |V| + 1$ for non-tree graphs. Thus if $|E(G)| = |V(G)| + 1$ then $G$ isn't a connected non-tree graph.

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