1.II .17F
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 has size , and deduce that every connected graph of order and size is a tree.
Let be a tree of order . Show that if is a graph with then is a subgraph of , but that this need not happen if .