Please ensure that your name and student number appear on the assignment, which must be submitted in a folder.
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):
|
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.
|