answers to practice probs for graph theory:

12/11/05


1. smallest nonplanar graph: K_5
2. smallest nonstar: K_3
3. smallest acyclic nonstar: P_4

 For v and w non-adjacent vxs in C_5:

4. two distinct paths join v and w in C_5
5. one of these paths has length 2; 
   the other has length 3

6. delta(G) is at most 3.

If G has fewer than 3 vertices, this is trivial.
Also, it suffices to show the result for G connected.
If G is connected and planar with girth 5, then 
m is at most (5/3)(n-2) so dn = 2m <= (10/3)(n-2),
where d is the average degree of a vertex in G.
Hence, some vertex has degree at most 3 - i.e.,
delta(G) at most 3.  In fact, even for girth = 4,
the result holds since one would then get d < 4.
(It follows that chi is at most 4 for such graphs.)

7.  bt(G U H) is at least max(bt(G),bt(H)) since
G U H contains G and H as subgraphs and bt is a
monotonic invariant (can't increase for subgraphs)

For the opposite argument, first take book embeddings
of G and H with v the first vertex for H and last for G
(in the linear order along the spine).  (This can always
be done by rotating the ordering along a circle before 
cutting the circle to make it the spine.)  Now G and H
can use the same pages and those pages of G which contain
v have it at the extreme right while those pages of H with
v have it on the extreme left so no conflicts at v arise.

8. omega(G U H) is at least the max by same argument above.
The reverse inequality holds since any edge in G U H
must lie either in G (and hence in all V(H) copies of G)
or in H.

9. Again one half of the result is trivial by the monotonicity
of chromatic number.  For the other, note that a coloring of
G and a coloring of H automatically color G U H.

10. The hard half is to show that the cartesian product G x H
doesn't need more than the max of chi(G) and chi(H).  Let r
be the larger of chi(G) and chi(H) and let G and H both be
colored using r (or fewer) colors.  Assign to vertex (v,w)
in G x H the color col(v) + col(w), where "+" means the mod-r
sum.  If (v,w) and (v',w') are adjacent in G x H, then either
v=v' and w and w' are adjacent in H or reverse G and H, etc.
But then col(v)=col(v') while col(w) not-= col(w') so
col(v,w) = col(v)+col(w) not-= col(v')+col(w') = col(v'w'),
so G x H has an r-coloring.

11. To show omega(G x H) is at most max(omega(G),omega(H)),
just note that every triangle in G x H either lies in G or H.
Indeed, if (v,w),(v',w') and (v'',w'') is a triangle in G x H,
then (wlog) v=v' and [w,w'] is an edge of H.  If v'=v'', then
[w',w''] is an edge of H.  Since (v,w),(v'',w'')  determine
an edge in G x H and v = v'', [w,w''] is an edge of H so
the triangle is really v x (w,w',w''), where the vertices
w,w',w'' determine a triangle in H.  On the other hand, if we 
had w'=w'', then [v',v''] is an edge of G and in particular v'
and v'' are unequal.  Hence, v and v'' are distinct.  But also
w and w' are unequal while w'=w'' so w and w'' would be 
distinct.  Hence, (v,w) and (v'',w'') would not be an edge
in G x H.