AMS303FstTestSoln

AMS 303 FIRST TEST REVIEW Questions and Solutions to Old Tests

REMEMBER THAT YOU MAY BRING ONE PAGE OF DEFINITIONS AND THEOREMS TO THE TEST (but no homework solutions or proofs of theorems)
Questions for 2008 AMS 303 First Test 1. What are the face and edge chromatic numbers of the graph on the right. Explain your answers. For graph, see separate link to 2008 First Test.
2. What is the chromatic polynomial of the graph on the right. For graph, se separate link to 2008 First Test.
3. Let G be a simgle connected planar graph. Explain the effect of the following operations on the number of vertices, edge, and faces in G and in the dual of G:
a) contract an edge; b)contract a triangular face.
4. Restate the following theorem in terms of the dual (DO OT PROVE): If G is a simple, connected planar graph with every vertex of deg at least 4, then G has at least one triangular face.
5. Show that if a planar graph G has all triangular faces and is vertex 3-colorable, then every vertex has even degree (don't quote any theorems).
6. If T is a trail from x to y in a simple graph, then prove that there exists a path from x to y formed by a subset of vertices and edges of T
7. Suppose that G is a connected, simple, planar graph in which each vertex has vertex 4.
a) Prove that m = 2f -4; b) Suppose every face has 3 or 5 boundary edges. Prove that there exists exact 8 more triangular faces than pentagonal faces.

Questions for 2007 AMS 303 First Test
1. What are the face and edge chromatic numbers of the graph on the right.
2. What is the chromatic polynomial of the graph on the right.
3. (i) What is the effect in the dual of contraction (to a point) a triangular face of G?
(ii) Must G's dual always be simple. Explain why true or give counterexample.
4. State the dual version of problem #7.
5. If a planar graph is know to be face 2-colorable, prove that the boundaries of the faces in its dual are all even (CANNOT QUOTE A THEOREM TO PROVE).
6. A bridge in a graph is an edge whose removal disconnects the (connected) graph. A graph G is critical k-chromatic if the minimal vertex coloring number is k and if any vertex x is removed, G-x can be k-1-colored. Show that if G is critical k-chromatic, then G cannot contain a bridge. Hint: Draw a picture.
7. If G is a simple, connected planar graph with less than 6 vertices, prove that G has a vertex of degree<=3.

Questions for 2005 AMS 303 First Test
1. What are the face and edge chromatic numbers of the graph on the right.
2. What is the chromatic polynomial of the graph on the right.
3. Let G be a simple, connected plane graph. Explain the effect of the following operations on the dual of G: a) Delete a vertex of G of degree 3 (or 5), b) Contract a face with 4 (or 3) bdy edges to a vertex, c) select a set of edges forming a circuit.
4. Re-state the following statement about a planar graph G in the dual: If G is a planar graph with every face having at least 4 boundary edges, then G has a vertex of degree at most 3.
5. Show that if a simple, cubic planar graph can be face 3-colored, then every face must have an even number of boundary edges.
6. Let G be any connected graph. If C is a set of edges forming a circuit in G and K is a set of edges forming a cutset, show that C and K must have an even number of edges in common (possibly zero). Reminder: A cutset K is a set of edges required to disconnect G into a two-component graph G-K.
7. Let G be a simple, planar grpah in which every face has exactly 4 bdy faces.
a) Show that m = 2n - 4.
b) Suppose every vertex has degree 3 or 4. Show that G has exactly 8 vertices of degree 3.

Solutions to 2008 AMS 303 First Test.
1. Test A: face chromatic no and edge chromatic no. is 3; Test B: k(k-1)^5(k-2)^7.
2. Test A: k(k-1)^4(k-2)^6; Test A: face chromatic no and edge chrom no is 3.
3. Test A: a) n-1, m-1, f; n*, m*-1, f*-1, b) n-2,m-3,f-1; n*-1,m*-3,f*-2. Test B: same as Test A; b) n-1,m-3,f-2;n*-2,m*-3,f*-1.
4. Test A: If G* is planar with deg >=3 and bdy>=4, then G has at least one vertex of deg 3. Test B: same as Test A question #5.
5. Test A: Triangular faces means neighbors of any vertex x form a circuit around x. If x has one color, vertices of circuit must be 2-colorable => even length circuit => x has even degree. Test B: Same as Test A question 6.
6. Test A: Starting from x, let z be the first vertex, if any, on T that is repeated. Remove the edges of T between the first and second visit to z. Go back to x and start along the reduced trail T' (without edges just removed) and again check for a repeated vertex z'. If z' exists, perform the same type of edge removal as above; then again restart at x along the further reduced trail. Continue until the reduced trail has no repeated edges; that is, it is a path.
7.a) 4n = sum(edg) = 2m => m/2 = n = m-f+2 => 2f-4 = m.
b) let f = f3 (no. of triangles) + f5 (no. of pentagons). Then 3f3 + 5f5 = sum(bdy) = 2m = 4f - 8 = 4f3 + 4f5 - 8 => f3 = f5 + 8.

Solutions to 2007 AMS 303 First Test
1. face chromatic no. is 4, edge chromatic no. is 3:
2. k(k-1)^9(k-2)^3(k-3).
3. (i) In dual, delete vertex of deg. 3.
(ii) Dual not simple, e.g., let G be a graph consisting of a 4-circult.
4. If G is connected planar with all deg >=3 and with less than 6 faces , prove that G has a face of bdy <=3.
5. The faces surrounding a vertex in G form a circuit. Since G is face 2-colorable this circuit must be even length. Thus each vertex of G has even deg implying that each face in G* has even boundary.
6. Let G1 and G2 be the two components when a bridge of G is removed. The chromatic number of G equals the larger chromatic number of G1 and G2. Say it is G1. Then removing any vertex in G2 will not decrease the chrom. no. of G. So G cannot have a bridge if it is critical k-chromatic.
7. simple means all bdy>=3. So 3f <= sum(bdy) = 2m --> 3(m-n+2) <= 2m --> m <= 3n - 6. Now assume result false so that deg >=4 and so 4n <= sum(deg) = 2m or 2n <= m. Combining with m <= 3n -6, we have 2n <= m <= 3n-6 --> n >=6. Contradication.

Solutions to 2005 AMS 303 First Test
1. Face chrom no = 4, edge chrom. no. = 5.
2. k(k-1)^7(k-2)^4(k-3).
3. a) Contract a face of bdy 3 (or 5) to a vertex, b) Delete a vertex of deg 4 (o3), c) select a set of edges forming a cutset.
4. If a planar graph has vertices of degree >=4, then G has a face of bdy <=3.
5. Consider the faces that surround a given face F. The surrounding faces must have common edges between successive faces so that they form a circuit of faces around F. If F gets color 1, then the surrounding circuit of faces must be 2- colorable, which means it must have even length. Then F has an even bdy.
6. The removal of the edges of the cutset K divide G into two components. Every circuit that crosses the cutset over to the other component must return across the cutset back to the component where it started-- this crossing and re-crossing can happen several times (or zero times).
7a) 4f = sum(bdy) = 2m --> 4(m-n+2) = 2m --> 2m - 4n + 8 = 0 --> m = 2n - 4.
b) 3n3 + 4n4 = sum(deg) = 2m = 4n - 8 = 4n3 + 4n4 - 8. --> 0 = n3 - 8 -->n3=8