A. Show that the tree-order associated with a rooted tree T is indeed a partial order on V(T), and verify the claims made about this partial order in the text.
B. Do the partition classes of a regular bipartite graph always have the same size?
C. Show that a graph is bipartite if and only if every induced cycle has even length.
D. Find a function f : N → N such that, for all k ∈ N, every graph of average degree at least f(k) has a bipartite subgraph of minimum degree at least k.