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 AMS 303 First Test Spring 2009
1. a) What is the face chromatic number of the graph at the right?
b) What is the edge chromatic number of the graph at the right?
2. Find the chromatic polynomial of the following graph:
3. Let G be a simple, connected plane graph. Explain in words the effect of these operations on the dual of G.
a) Delete an edge of G. b) Delete a vertex of G whose degree is 5 c) select a set of edges forming a cutset
4. Re-state the following statement about a planar graph G in the dual: If a planar, connected simple graph G has less than 6 vertices, then G must have a vertex of degree =< 3. (DON'T PROVE; JUST RESTATE FOR DUAL)
5. If a planar graph can be vertex 2-colored, prove that this implies that every vertex in the dual has even degree (YOU MAY NOT QUOTE ANY THEOREMS: PROVE THIS RESULT YOURSELF).
6. Suppose that a graph G has two different circuits C and C' that each contain the edge e. Show that G must have a third circuit C" that does not contain e. Show how some of edges in C and C' can be used to construct a new circuit that does not contain e. Remember that circuits have no repeated vertices.
7. If G is a simple, planar graph with all vertices of degree 5 or 7. Prove that G has at least 12 more vertices of degree 5 than vertices of degree 7.
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 NOT 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.

Solution to First Test, Spring 2009
1.a) faces can be 4 colored: the infinite face and three faces touching it are mutually adjacent (their dual is a K4) or so fewer colors not possible.
b) edges cab be 4-colored: max degree is 4 and so fewer colors do not work.

2. Test A: k*(k-1)^11*(k-2)^7*(k-3)^2; Test B: k*(k-1)^10*(k-2)^6*(k-3)^2.

3. Test A (4 Test B): a) contract edge in G*, b) contract face of bdy 5 in G*, c) select a circuit in G*

4. Test A (3 Test B). If a connected planar graph G* with all degrees >=3 has fewer than 6 vertices, then G* has a face with bdy <= 3.

(6 Test B) Vertex 2-colored implies all circuits have even length (otherwise vertices on a circuit could not be 2 colored). Since boundaries of regions are circuits, all boundaries have even size. In dual, this means all vertices has even degree.

5. Test A (6 Test B) Vertex 2-colored implies all circuits have even length (otherwise vertices on a circuit could not be 2 colored). Since boundaries of regions are circuits, all boundaries have even size. In dual, this means all vertices has even degree.

6. Test A (5 Test B) Note that the two circuits, call them C and D, may have many edges in common, possibly also some additional vertices where they cross. Let the endvertices of the edge e be u and v. Let P and Q be the associated paths from u to v of C and Cb when edge e is deleted. Start from u along P. Let r be the last vertex of P (starting from u) that is common to both P and Q (possibly r = u). Thus, the edge on P after vertex r is not an edge of Q. Build our circuit as follows. Start from r and go along P until we encounter a vertex s that is again also on Pb (in the extreme case, s = v, the far end of both paths). Next follow the other path Q from s in the direction back towards u stopping when we reach r. By the choice of r and s, a circuit is formed when we follow P from r to s and then Q from s back to r.

7. Simple imples 3f <= sum of boundaries = 2m. Combined with f = m - n +2, we get m <= 3n-6. Let n5 and n7 be the numbers of deg-5 and deg-7 vertices, respectively. Then n = n5 + n7 and
5n5 + 7n7 = sum(degrees) <= 6n - 12 = (6n5 + 6n7) - 12
Simplifying this equation, we get n7 <= n5-12.
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