Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Math 137A Assignment 4
1. * Prove that if χ(G) = k , then G has at least 
edges.
2. * Let G have chromatic number k and suppose you are given a k- coloring of G. Prove that for each color i, there is some vertex colored i that is adjacent to vertices of each of the other k − 1 colors.
3. A graph G is color-critical if χ(G − v) < χ(G) for every vertex v (i.e., deleting any vertex reduces the chromatic number). Prove that if G is a color-critical graph, then the graph G′ constructed from G using Mycielski’s construction is also color-critical.
4. Prove that the chromatic number of the graph below is 4. Hint: To show that χ(G) > 3, start by classifying the independent sets of size 4 . Show that when deleting any such independent set, the resulting graph is not bipartite. Why does that suffice?
5. * Calculate the chromatic polynomial of the following wheel graph:
6. * Prove that the chromatic polynomial of the ladder graph with 2n vertices pictured below is (k2 − 3k + 3)n−1k(k − 1).
7. * Recall that the Tutte polynomial of a graph G = (V, E) is defined as
where k(A) is the number of components of the subgraph (V, A).
For this question, if G is connected, then verify that TG(1, 1) equals the number of spanning trees of G. Note: we adopt the convention that 00 = 1.
8. * Prove that every cubic Hamiltonian graph has chromatic index 3. Conclude that the Petersen Graph is not Hamiltonian.
9. * If G is k-regular and connected but there is a vertex v such that G − v is disconnected, then prove that χ′ (G) = k + 1.