3
Proving 2,3 implies 1:
We have an acyclic graph $G=(V, E)$ with $n-1$ edges. We want to prove that $G$ is a connected graph.
Assume for the sake of contradiction that $G$ is not connected. This means we have $d>1$ connected components, $G=\{\bigcup_{i=1}^{d}G_i\}$.
Since $G$ is acyclic, each connected component is a tree by definition. Let $V_i$ be the ...
2
Let us prove by induction that any tree on $n$ vertices has at least $2^{n-1} - n$ induced disconnected subgraphs.
When $n = 1$, this is clear since $2^{n-1} - n = 0$. Now suppose $n > 1$, and let $T$ be a tree on $n$ vertices. Choose an arbitrary leaf $v$, let $T'$ be the tree obtained by removing $v$, and suppose that $v$ is connected to $u \in T'$. By ...
1
In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find Chapter 4. Crown decomposition. This should point you to the answer.
Only top voted, non community-wiki answers of a minimum length are eligible
