Graph Theory: Trees, leaves and cycles

Question

So, a vertex is called a leaf if it connected to only one edge.

a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that $G = (V, E)$ is a graph, $V \neq \emptyset$, where every vertex has at least 2 edges, Show that $G$ has a cycle.

I don't really know for sure how to write the proofs for these two tasks, but here is what I have

a) So between two points $u$, $v$ in the graph there is always exactly one path, and if $G$ is a tree it is connected. For a graph with $e=1$ edges you will have $n=e+1$ vertices. Is there any more to it than this? Do I have to include something else?

b) So $G$ is a connected graph iff $G=(V,E\setminus\{e\})$ has a cycle that contains $\{e\}$. Now, every node has the degree 2, meaning they are connected to vertices. This also means that the end vertex is connected to 2 vertices. Very simplified I have written

$$ u,v \in V \\ V = \{u(n),......u(n+1), v\} $$ Now, if $G$ did not contain any cycles that would be it, but since $v$ is connected by 2 vertices it means it is reachable by another vertex than $u(n+1)$ right? Having a problem showing this in a sensible way.

Thanks in advance.

Answer 1

a) Trees are minimally connected, meaning the deletion of any edge disconnects the graph (into two nontrivial trees unless your graph is very special). By strong induction, these two trees each have at least two leaves. What can you conclude about the original tree?

b) Since every vertex has degree at least two, you could consider a subgraph wherein every vertex has degree exactly two. Do you know a famous result about graphs whose vertices are all of even degree?

Answer 2

To prove (b) let $v_0$ be any vertex. Since $\deg v_0\ge 2$, there is a vertex $v_1$ such that $\{v_0,v_1\}$ is an edge of $G$. Similarly, there is a vertex $v_2$ different from both $v_0$ and $v_1$ such that $\{v_1,v_2\}$ is an edge of $G$. Keep going: given $v_{k-1}$ and $v_k$, there is a $v_{k+1}$ different from both $v_{k-1}$ and $v_k$ such that $\{v_k,v_{k+1}\}$ is an edge of $G$, and if possible we’ll choose $v_{k+1}$ to be different from $v_i$ for all $i\le k$. $V$ is finite, so eventually we’ll run out of unvisited vertices, and we’ll have to choose $v_{k+1}=v_\ell$ for some $\ell<k-1$. You know have a cycle: what is it?

You can prove (a) by induction on the number $n$ of vertices of the tree. First notice that (b) implies that every tree has at least one leaf; why? Now suppose that every tree with $n$ vertices has at least two leaves, and let $T$ be a tree with $n+1$ vertices. $T$ has a leaf $v$; let $T'=T-v$, the graph obtained from $T$ by removing $v$ and the one edge attached to it. Check that $T'$ is a tree and hence by the induction hypothesis has at least two leaves; then show that at least one of these leaves is also a leaf of $T$.