Back to graph theory page

Graph Theory: Practice Problems 11/13/05

1. Find an embedding of K_5 in the Moebius band. (fairly easy)

2. Find an embedding of K_7 in the torus. (moderately difficult)

3. Let G be a connected graph with girth g(G) at least 5.
Give a lower bound on the genus of G in terms of g, n=|VG|,
and m=|EG|.  You don't need to prove it.  (easy)

4. Show that the genus of the Petersen graph is 1; gamma(P)=1.
                                           (moderately difficult)

5. Prove that gamma(K_p,p) is at least {(p-2)^2/4} (quantity (p-2)-squared
divided by 4 and rounded up to the nearest integer).  Easy

6. Find the intersection graph of the family of sets determined by
the 7 words in quotes: "Of man's first disobedience and the fruit"...
                                                      Easy

7. Show that if G is Eulerian, then LG is Eulerian.   Easy

8. Show that if G is Hamiltonian, then LG is Hamiltonian.  Moderate

9. T or F?: H is isomorphic to LG for some G if and only if every
     vertex of H is in at most two cliques of H.      Easy

10. Show that every graph is an intersection graph.   Easy

11. Prove bt(Q_d) is at least {d/2}.                  Actually, hard
 The lower bound comes out to be d/2 using a rather lengthy argument.
So don't worry about this one - but you should be able to do the
Hamiltonian case below which is much easier 

bt_Ham(Q_d) = d-1

at least the lower bound is very easy and the fact that it is 
achievable involves taking two mirror-image copies of Q_(d-1)
in d-2 pages, then adding a page with the matching of vertices
in each copy which forms the graph Q_d and uses one extra page,
so Q_d needs only d-1 pages given the inductive assumption that
Q_(d-1) needs at most d-2. 

12. T or F?: G is planar implies that bt(G) is at most 2.  Difficult

13. Is bt_1(G) at most Delta(G) when G is bipartite?  Unsolved problem!

14. The following facts can be proved:

A. Every outerplanar graph is the edge-disjoint union of two acyclic graphs.
B. Every acyclic graph is the edge-disjoint union of two star-acyclic graphs.

Use A and B to prove that for any G, bt^2(G) is at most 4*bt(G),
where we write bt^2 for book thickness where pages have diameter at most 2,
not as a squaring operator. See the 
midterm-background page  for this and other notation.

15. Prove B.

Back to graph theory page