Suppose we want to prove that any connected graph G = (V, E) with |V| =...

 

Transcribed Image Text:

Suppose we want to prove that any connected graph G = (V, E) with |V| = |E| + 1 is a tree, i.e. the implication (v) (i) in Theorem 5.1.2. 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. Suppose we want to prove that any connected graph G = (V, E) with |V| = |E| + 1 is a tree, i.e. the implication (v) (i) in Theorem 5.1.2. 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.

Answer rating: 100% (QA)

For this we have to prove the followingtheorem Let G be a ... View the full answer