Comp 7750/4060 Graph Algorithms

Assignment 3

Sept - Dec 2018 
assigned 22 Nov, 2018
due 6 Dec, 2018

Please ensure that your name and student number appear on the assignment, which must be submitted in a folder.


Written Answers (100 points or 120 points)

1. Let cn denote the chromatic polynomial of a cycle Cn,
eg. c3 = λ(λ-1)(λ-2).
Write a recurrence for cn in terms of cn-1 and solve it for all n.
2. How many perfect matchings do K4 and K6 have? How many
1-factorizations do they have? List them.
3. Let K be a 3-regular graph. Show that G has a minor K iff G has a subgraph TK.
Note: Minors are formed by deleting edges or contracting edges.
4. Prove that if G is a k-regular bipartite graph with k > 1 then G has no cut-edge. Hint: If G has a cut-edge uv, count the number of edges in each component of G-uv, by summing the degrees.
5. A graph is Eulerian if it is connected and all degrees are even. Show that a planar graph is bipartite iff its dual is Eulerian.
Hint: Show that every cycle in the graph must have even length.
6. Let G be the graph formed from K5 by removing two non-adjacent edges. Find the chromatic polynomial of G using the recursive method.
7. Use Christofides' algorithm to find a travelling salesman's circuit in the graph shown. Be sure to show the minimum spanning tree T, the matching M, and the cycle C found. Compare the weight of C with the weight of T and of T+M.

    

8. Compute the spanning tree bound for the TSP-instance of question 1.
9. The 3-cube, Q3 has vertex set V consisting of all binary vectors of 3 bits. Two vertices u=(a1,a2,a3) and v=(b1,b2,b3) are adjacent if they differ in exactly 1 bit. Draw a picture of Q3, such that the vertices are labelled by the binary vectors of length 3. Show that the 4-cube, Q4, contains at least 8 copies of Q3. Hint: how many 3-vectors does a 4-vector contain?
10. Determine by hand whether the graphs shown are hamiltonian.

        
    

Nicer drawings of the first 2 graphs (but with a different numbering):

        

Questions 11, 12 are for students in 7750 only

11. Let G be a Moore graph of degree k with n vertices. Let v be any vertex of G. Show that the number of hexagons containing v is exactly
k(k-1)2(k-2)/2, and that the number of heptagons containing v is exactly
k(k-1)2(k-2)(k-3)/2. Find a formula for the total number of hexagons and heptagons in G. Subsitute k=3 to obtain the counts for the Petersen graph.
12. Determine whether the graph shown is the line graph of some graph G. If so, find G.

graph

No programming question.