4
$\begingroup$

If a graph $G$ has $n$ vertices and $n-2$ edges and no isolated vertices (no connected component has only one vertex) we want to show that at least $2$ of its connected components are trees with at least $2$ vertices each.

I tried contradiction by supposing we have at most $1$ tree with at least $2$ vertices, which means either we had such a tree or not. In case we don't have such a tree, since the component is connected, I'm trying to get a contradiction by supposing that each of the components has at least $1$ cycle, but I haven't got further.

$\endgroup$

2 Answers 2

1
$\begingroup$

a connected component on $c$ vertices has at least $c-1$ edges, with equality only if the component is a tree with at least $2$ vertices or is an isolated vertex. Therefore adding over all components we get the number of edges in $G$ is larger than or equal to $n-t$ where $t$ is the number of components that are trees with at least $2$ vertices.

$\endgroup$
1
$\begingroup$

The Euler characteristic $\chi(G)=V-E$ of a connected finite graph satisfies $\chi(G) \le 1$ with equality if and only if it is a tree.

For a disconnected finite graph $G$ with components $G=G_1 \cup \cdots \cup G_K$, we have $$\chi(G) = \chi(G_1) + \cdots + \chi(G_K) $$ Your graph $G$ has $\chi(G) = n - (n-2)=2 > 1$, so it is disconnected. In order for the above sum to be equal to $2$, at least two terms have to be $\ge 1$. But each term is $\le 1$. So at least two terms are $=1$. Thus, at least two of the components of $G$ are trees.

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