2
$\begingroup$

Prove that if G is connected and acyclic then G is connected and has n-1 edges.

My attempt at a solution, (I'm concerned there is an error in the inductive step):

Proceed by strong induction on n the number of edges.

Base Case: For $n=1$ we have an isolated vertex, which is connected and acyclic and we have $1-1 = 0 $ edges.

Inductive Step: Assume that the claim is true for all $1 \leq n \leq k$. That is every connected and acyclic graph with n vertices is connected and has n - 1 edges.

Inductive Hypothesis: We now prove the claim for $n = k+1$ vertices. Remove an arbitrary vertex $v \in V$ and its adjacent edges. There are now two possible cases, let $G^*$ be the graph obtained by removing vertex $v$. $G^*$ can either be connected or disconnected. In the case in which $G^*$ is connected, then we have k vertices and by the induction hypothesis we know the claim holds. In the case in which $G^*$ is disconnected, then we have two connected components. Let one component have q vertices and let the other component have w vertices such that $q + w = k$ and $1 \leq q,w < k$. By the inductive hypothesis we know that both of these connected components have $q -1$ and $w -1$ edges. If we add an edge to connect these two components we then have $q-1 + w-1 +1 = q + w -1 = k -1 $. edges. Therefore, by the principle of induction the statement is true.

$\endgroup$
  • $\begingroup$ Where it says Proceed by strong induction on n the number of edges. -- is it part of the question? If it is, then it sounds like you're told that $n$ denotes the number of edges, not the number of vertices. But your solution, which may or may not be correct (I haven't read it carefully yet), doesn't follow this requirement, because you use $n$ to denote the number of vertices instead. $\endgroup$ – zipirovich Jan 11 at 21:21
2
$\begingroup$

It's simpler to remove an edge from $G$ rather than a vertex in the inductive case.

In the case in which $G^∗$ is connected, then we have $k$ vertices and by the induction hypothesis we know the claim holds.

You need to add back why $G$ has $k+1$ edges.

In the case in which $G^∗$ is disconnected, then we have two connected components.

This isn't true. Consider the following graph with the center vertex removed.

SimpleGraph

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