answer all for practice

la) What is the face chromatic number of the graph at the right? b) What is the edge chromatic number of the graph A G m at the right? B h 2. Find the chromatic polynomial for the graph on the right. 3. Let G be a simple, connected plane graph. Explain the effect of the following operations on the number of vertices, edges and faces in the dual of G . a) contract an edge; b) contract a triangular face . 4. Restate the following theorem in terms of the dual graph (DO NOT PROVE): If G is a simple connected planar graph with every vertex of degree at least five. then G has at least three triangular faces. 5. A bridge in a graph is an edge whose removal disconnects the graph. A graph G is critical k-chromatic if the minimal vertex coloring number is k and when any vertex x is removed, the minimal vertex coloring number of G-x will be k-1. E.g.. an odd-length circuit is critical 3-chromatic. Show that if G is critical k-chromatic, then G cannot contain a bridge. Hint: draw a picture. 6. Show if a planar graph G has all triangular faces and is vertex 3-colorable, then every vertex has even degree. 7. Suppose that G is a connected, simple planar graph in which each vertex has degree 4 (all deg = 4). Suppose that every face has 3 or 5 boundaries; that is, every face is triangular or pentagonal Prove that there are exactly 8 more triangular faces than pentagonal faces