AMS 303 Quiz Review

2011 Quiz Questions
1. Suppose that every vertex in a graph G has degree at least 2. Prove that G has a circuit.
2. Let G be a simple planar graph with fewer than 12 vertices.
a) Prove that m <=3n-6; b) Prove that G has a vertex of vertex <=4.

2010 Quiz Questions
1. Show that if the removal of a vertex x disconnects the connected graph G then there exist vertices a and b in G such that every path in G between a and b passes through x.
2. Let G be a planar, simple graph with each vertex of degree >= 3. a) Show that m <= 3f - 6. b) Show that G has a face bounded by at most 5 edges.

2009 Quiz Questions
1. If T is a trail from vertex x to vertex y in a simple graph G (recall that a trail may repeat vertices but does not repeat edges), then prove that there exists a path P (with no vertices repeated) from x to y formed by a subset of vertices and edges of T.
2. If a planar, connected graph G with deg(x) => 3 for all x and if G has less than 6 faces, show that G must have a face of boundary =< 3. First use the fact that deg(x) => 3 to show that m =< 3f-6. Next assume the conclusion (i.e., there is a face of bdy =< 3) is false and get a contradiction f < 6.

2011 Solutions
1. Start at any vertex and trace out a path P without repeating edges. Any vertex entered for the first time can be exited by a different edge since deg >=2. Eventually some vertex w must be repeated. The edges of P between the first and second visit to w form a circuit.
2. a) simple --> bdy >=3. So 3m - 3n + 6 = 3f <= sum(bdy) = 2m --> m - 3n + 6 <=0 --> m <= 3n - 6.
b) Assume all deg >= 5 --> 5n <= sum(deg) = 2m <= 3(3n-6) = 6n - 12 --> 5n <= 6n - 12 or 12 <= n. But n < 12. This contradiction proves that there is a vertex of deg <=4.

2010 Solutions
1. Let G1 and G2 be two components of G-x. Pick a in G1 and b in G2. Then every path in G betweeen a and b must pass through x since there is no path in G-x from a to b.
2. a) 3n <= sum(deg) = 2m --> m-f+2 = n <= 2/3m --> (1/3m) - f + 2 <= 0 --> m <= 3f - 6.
b) assume all bdy >=6. Then 6f <= sum(bdy) = 2m (by part a) <= 2(3f-6) = 6f-12. This contradiction proves there is a face with 5 or fewer boundary edges.

2009 Solutions
1. Let v be the first vertex on the trail from x to y that is encountered twice (if no such v, trail is a path). Delete all the EDGES (not vertices) between the first and second visit to v. Now take the reduced set of trail edges and do the same traversing from x looking for a repeated vertex. Repeat this process until a path from x to y is obtained.
2. 3n =< sum of deg = 2m ==> n =< (2/3m). Combining with n = m-f+2, we get m <= 3f - 6. Now assume all bdy >=4. Then 4f <= sum of bdy = 2m <= 6f - 12. Hence 4f <= 6f - 12 or f>= 6. Contradiction.