Math 137A

Final Exam Spring 2023

1.  (6 points) Draw all simple graphs  (up to isomorphism) which have exactly 5 vertices and 5 edges. Why is your list complete?

2.  (2 points each) Each statement below is false. Verify this fact by,  for each statement, drawing a simple graph that serves as a counterexample.

(a)  A graph with n vertices and n − 1 edges is a tree.

(b)  Every Eulerian graph is Hamiltonian.

(c)  Every graph G satisfies χ(G) ≤ ∆(G).

(d)  If G hasn vertices and contains a Hamilton cycle, then every vertex v ∈ V (G) has deg(v) ≥ 2/n.

(e)  Any maximum matching in a connected graph G with at least 4 vertices must contain at least two edges.

(f)  If G is 2-connected but not 3-connected, then G has a vertex of degree 2.

3.  (4 points) Let G be a connected planar graph with e edges, U vertices and where all faces have length at least 5. Prove that

4.  (4 points) A wheel  graph Wn is constructed by taking an n-cycle, adding a new vertex and joining this vertex to every vertex. For example, W3 = K4 and W4 is below. Calculate the chromatic number of Wn for all n. Hint: the answer depends on whether n is even or odd.

5.  (5  points) Please answer one of the following two questions. Points will be awarded based on correctness and amount of detail provided.

•  What is the relationship between edge-colorings of Kn,n  and Latin squares of order n?  In other words, how can you go from one to the other?

•  How exactly would you construct a de Bruijn sequence of order 1000 using an Eulerian circuit? Included in your answer should be any definitions of graphs you are using, why an Eulerian circuit exists, and how it can be used to obtain a de Bruijn cycle.

6.  (2+3 points) As you should know well by now, the  Chebyshev  Metric  on Z2 measures the distance between points (i, j) and (k , ℓ) to be

max(|i - k|, |j - ℓ|).

For example, the distance between (1, 1) and (2, 3) is 2.  Given the points below, suppose all edges exist but are not drawn (in other words we have the complete graph) and that the cost of traveling between two points is given by the Chebyshev metric.

In this question you will use Christofides’ Algorithm to find a Hamilton cycle whose cost is at most 3/2 the cost of the cheapest Hamilton cycle.

(a)  Find a minimum cost spanning tree of the points below. Do this and draw the result below:

(b)  Copy the tree you found in Part (a) above, and complete the next step of the algorithm here.

(c)  Copy your answer from part (b) here, and then complete the final step of the algorithm.