AMS 303 Quiz Review

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. 2008 Quiz Questions
1. Let G be any connected graph. If C is a set of edge 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).
2. Let G be a connected planar graph in which every face has boundary >=4.
a) Prove that m <= 2n-4.
b) Suppose that every vertex has degree 3 or 4. Show that G must have at least 8 vertices of deg. 3. Hint: write n as n = n3 + n4.

2007 Quiz Questions
1. Suppose that G is a simple graph this is not connected. Prove that the complement of G must be connected; that is, there is a path between every pair of vertices in G. Hint: Connecting paths will have 1 or 2 edges.
2. Let B be a connected, simple, planar graph, with all degrees at least 4.
a) Prove that m <= 2f-4.
b) From a), show that G must have at least one face bounded by 3 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.
2008 Solutions
1. Let G1 and G2 be the 2 components of G-K. Suppose the circuit starts in G1. Each time, if ever, that it uses an edge in K to go from G1 to G2 it must use another edge in K to get back to G1. Hence C uses an even number of edges of C.
2. a) This is the exact dual of problem 2a in 2007.
b) 3(n3)+4(n4) = sum(deg) = 2m = 4n - 8 = 4n3+4n4 - 8 => 3n3 <= 4n3 - 8 => n3 >= 8.

2007 Quiz Solutions
1. Let G1 be one component of G and let G2 be the rest of G. In the complement, if x in G1 and y in G2, they are joined by an edge. If x,y in G1, then there is a path x-z-y where z is any vertex in G2; similarly if x,y in G2.
2. a) 4n <= sum(deg) = 2m => (1/2)m >=n = (by Euler formula) m-f+2. Thus, 0 >= (1/2)m-f+2 or f-2 >= (1/2)m or 2f -4 >= m.
b) Suppose false and all bdy >=4, Then 4f <= sum(bdy) = 2m = 4f-8. Im possible.