Math 137A Assignment 5

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 137A Assignment 5

1. * It is conjectured that every maximal planar graph G (planar graphs where all faces are triangles) satisfy χ′ (G) = ∆(G). Prove that this conjecture is true when G is the icosahedron.

2. Prove that the flower J3 defined in class is a snark (that is, χ′ (J3) = 4).

3. * Prove that a tree T has at most one perfect matching.

4. * Two people play a game as follows. On a graph G, they alternate selecting vertices v1, v2, . . . so that at every step a path is formed. The last player who can select a vertex is the winner. Prove that the second player has a winning strategy if and only if G has a perfect matching.

5. * Determine whether or not the following graphs have a perfect match-ing by either finding a perfect matching or finding a subset S of one side’s vertices that violates the condition of Hall’s Theorem.

6. * 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 8 points below, suppose all edges exist but are not drawn (in other words we have the complete graph K8). Suppose the cost of traveling between two points is given by the Chebyshev metric.

Use Christofides’ Algorithm to find a Hamilton cycle whose cost is at most 3/2 the cost of the cheapest Hamilton cycle.

7. Repeat the previous question where now the set of vertices consists of all (i, j) ∈ Z2 such that i + j even and 0 ≤ i, j ≤ 4.