Reference no: EM13926868

1. 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.

Hint: Theorem 1.5.1.

2. Do the partition classes of a regular bipartite graph always have the same size?

Hint: Count the edges.

3. Show that a graph is bipartite if and only if every induced cycle has even length.

Hint: Show that if a graph contains any odd cycle at all it also contains an induced one.

4. 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.

Hint: Given a graph G, how would you split its vertex set into two parts A and B so that the bipartite graph H defined by the A-B edges of G has minimum degree as large as possible? To find f, apply this method to a suitable subgraph G of a given graph G’, and determine how large d(G’) must be to ensure that δ(H) ≥ k.