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 ≠ Ø, 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{e}) has a cycle that contain {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 ∈ 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.
Best Answer
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?