Prove a graph is cyclic

Question

I encountered the following problem:

Let $G(V, E)$ be a finite undirected graph with $2n$ vertices, in which every connected component has an even number of vertices. Given that exactly $n$ of the vertices of $G$ have a degree at least $3$, prove that $G$ is cyclic.

My solution to the problem goes as follows:

Let $C$ denote the set of all connected components $G_i(V_i, E_i)$ of $G$ and $|C| = k$.

Let's assume that $G$ is acyclic. That means that every $G_i$ is a tree. Then, by adding exactly $k-1$ edges to $G$, we can connect all connected components in such a way (root of one to another one's leaf, ordering them in a sequence that way) that we obtain a tree $G'(V', E')$, where $V'= V$ and $|E'| = |E| + k - 1$.

But since $G'$ is a tree, that means that $$|E'| = |V'| - 1 = |V| - 1 = 2n - 1$$

By the handshake lemma we also know that $$2|E'| = \sum_{v\in V'}\deg v \ge \underbrace{3n}_{\substack{\text{atleast $n$}\\ \text{with degree $\ge$ 3}}} + \underbrace{n}_{\substack{\text{G' is connected}\\\text{$\Rightarrow$ the remaining $n$ have $\deg\ge 1$}}}$$

Thus we obtain that $$2(2n-1) \ge 4n \Leftrightarrow -1 \ge 0$$ which is a contradiction, hence $G$ can't be acyclic and contains a cycle.

Now, what bothered me about that is that I never used the given fact, that every $G_i$ had an even number of vertices, so I felt like I was missing something huge or my solution is flawed in a fundamnetal way... and I really banged my head against the wall hard enough, but was nonetheless unable to figure out what was wrong. So my question would be: am I missing something or is the mentioned statement in the problem simply redundant? And if it is redundand, how would one go about proving it? I really got stuck somewhere about there.

Many thanks in advance!

Answer 1

It seems even a little simpler than that, once we can show:

Lemma: Any tree has more leaf nodes than degree-3 and higher nodes.
Proof: Let a graph $G$ be a tree on $n$ vertices with $\ell$ leaf nodes and $h$ vertices of degree $3$ or more. Then $G$ has $n{-}1$ edges and by handshaking we know:
$2(n-1) = \sum d(v_i) \; \geq \; \ell + 2(n-\ell-h) + 3h = 2n-\ell+h,\quad$ so $\ell-2\geq h$ as required.

So the fact that half the nodes are degree $3$ or more shows that not all components are trees; i.e. that $G$ contains cycles. We could join components into a tree but it isn't really needed.

(thanks to jlammy for a compact statement of the lemma proof)

Answer 2

Here's something simple we can deduce from the extra hypothesis: because every connected component has an even number of vertices, there can be no vertices of degree $0$. This leads to a version of your argument that skips the "connect all the components" step.

That is, suppose by way of contradiction that $G$ is a union of $k$ trees. It's known that a forest with $2n$ total vertices and $k$ components has $2n - k$ edges. Therefore by Handshake we have $$\sum \deg(v_i) = 2|E| = 4n - 2k.$$

Now, $n$ vertices have degree at least 3, and $n$ vertices have degree 1 or 2. Therefore $$\sum \deg(v_i) \ge 3n + n = 4n.$$

Putting this together, we get $$4n \le 4n - 2k \implies k \le 0,$$ a contradiction.

Remark: I don't see anything wrong with your argument, so maybe the inclusion of the hypothesis is just to make life a bit easier?