Question

(5) Let G be a graph without loops. Let n be the number of vertices and let xG(z) be its chromatic polynomial. Recall from HW5 that 2(G) is the number of cycle-free orientations of G. Show that

Answer 1

Given that let 'G' be a graph without Loops. Let 'n' be the number of vertices. and let, X_ct (z) be its chromatic polynomial & ohm (a) is the number of cycle free. Orientation of c_t. To show ohm (c_t) = (-1)^n X_a (-1) For an empty graph, ohm (k^-_n) = 1 so, it holds Now consider a non-empty graph c_2 with an edge 'e' selected. Suppose we have an orientation G^rightarrow_e on all edges except 'e' and we would like to find out how many ways (i.e., 0, 1 or 2) we can extend it to an cycle free orientation C^rightarrow_2 on G Note: - that if there exists such an cycle-free orientation at all, removing the edge e won't break it on the other hand, if we can't add e in either direction because both would close a directed path in G^rightarrow_e into a cycle, then, these two paths make up a cycle in G^rightarrow_e by themselves. \r\n < null >