Hw6, due Tuesday 8/1
1. Suppose the odd cycles in G are pairwise intersecting, meaning
that every two odd cycles in G have a common vertex. Prove that
the chromatic number (minimum number of colors necessary to color the
vertices of G so that there's no edge between vertices of the same color)
of G is <= 5.
2. Prove that every n-vertex plane graph G (a planar embedding of a
planar graph) isomorphic to its dual, G^* has 2n-2 edges. For each n >= 4,
construct a simple n-vertex plane graph isomorphic to its dual.
(G^* has a vertex for every
face of G, and edge between vertices iff the corresponding faces in G share
an edge; G^* might be a multigraph even if G is simple)
Solutions
1.Delete the vertices of some odd cycle, C. Since every odd cycle
intersects C, it's deletion ensures that at least vertex is removed from
every odd cycle in G, hence G-C is bipartite and can be colored using at
most 2 colors. C can be colored using 3 colors (since removing a vertex
from C yields a bipartite graph), so in total it takes at most 5 colors
to color G. Note that the problem provided extra information. All that
was really needed was the fact that G had some cycle which intersected all the
odd cycles.
2.Euler's formula tells us that n-e+f=2 for planar graphs. For
self-dual graphs we have n=f, so 2n-2=e. Note that different emebddings
(drawings) of a planar graph may yield different duals. An n-vertex
wheel is a cycle on n-1 vertices and an additional vertex connected to
the n-1 others. When it's embedded to look like a wheel with n-1 spokes,
we have that such a graph is self-dual for n >= 4.