AMS 303 Quiz Review

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.

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.

2005 Quiz Questions
1. Show that the removal of a vertex x disconnects the connected graph G if 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 at least 3.
a) Show that m <= 3f-6, b) Show that G has a face bounded by at most 5 edges.

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.

2005 Quiz Solution
1. If all paths between a and b go through x, then removing x eliminates all paths betweens a and b. Thus the graph is no longer connected.
2. a) 3n <= sum of degrees = 2m --> n <= (2/3)m --> m-f+2 <= (2/3)m --> (1/3)m <= f-2 --> m <= 3f - 6.
b) Assume false so that a;; bdy >=6. Then 6f <= sum of bdy = 2m <= 2(3f-6) --> 6f <= 6f - 12. Contradiction.