1.II .17F

Graph Theory
Part II, 2005

Show that an acyclic graph has a vertex of degree at most one. Prove that a tree (that is, a connected acyclic graph) of order nn has size n1n-1, and deduce that every connected graph of order nn and size n1n-1 is a tree.

Let TT be a tree of order tt. Show that if GG is a graph with δ(G)t1\delta(G) \geqslant t-1 then TT is a subgraph of GG, but that this need not happen if δ(G)t2\delta(G) \geqslant t-2.