Math137A
Final Exam, June 9th, 2022
1. Show that if a connected graph on n vertices has n + 1 edges, then it must have at least two cycles.
2. Draw all graphs (up to isomorphism) with 5 vertices and 5 edges.
3. For the graph below, find a minimum spanning tree. Then use this to find a Hamiltonian cycle with cost at most 1.5 times the cost of the cheapest Hamiltonian cycle. Numbers beside edges are their costs and you may assume they satisfy the triangle inequality. The next page is blank which you can use to continue this question if needed.
4. Let G be a simple graph with 9 vertices and 34 edges. Show that G is not Eulerian. Hint: How many edges does K9 have?
5. Prove that if G contains at least one odd cycle, then it has at least one induced (or “chordless”) odd cycle.
6. Let G be a simple cubic planar graph. Let φk denote the number of faces in G of length k.
(a) Prove that
3φ3 + 2φ4 + φ5 − φ7 − 2φ8 − · · · = 12.
(b) Deduce that G has at least one face of length at most 5.
7. If G is a k-regular graph on an odd number of vertices, prove that χ′ (G) = k + 1.
8. Prove that if G is a graph in which any two odd cycles intersect, then χ(G) ≤ 5. Hints: You may want to use the result of Question 5. Also, what happens if an odd cycle is deleted?
9. Let T be a tree on n vertices. Show that the chromatic polynomial of T is
χT (x) = x(x − 1)n−1 .
10. A vertex cover in a graph G is a subset C ≤ V (G) with the property that every edge in G has at least one endpoint in C.
Prove that in a bipartite graph, the minimum size of a vertex cover equals the maximum size of a matching. Hint: Add two new vertices and use the MaxFlow - MinCut Theorem.
11. For the following network (edge labels are the edge capacities) find a maximum (s, t)-flow. Prove it ’s maximum by finding a minimum capacity cut.