Let G (V, E) be a loop free undirected graph (a) For each such graph, where V 3, find P(G, ) and show that in it the terms contain consecutive powers of Also show that the coefficients of these consecutive powers alternate in sign (b) Now consider G (V, E), where V n 4 and E k Prove by mathematical...

a V 1 P G V 2 E 0 P G 2 E 1 P G 1 2 V 3 E 0 P G 2 E 1 P G 2 1 3 2 E 2 P G 1 2 3 2 ...

Let G = (V, E) be a loop-free undirected graph. (a) For each such graph, where |V|

Question:

Let G = (V, E) be a loop-free undirected graph.
(a) For each such graph, where |V| ≤ 3, find P(G, λ) and show that in it the terms contain consecutive powers of λ. Also show that the coefficients of these consecutive powers alternate in sign.
(b) Now consider G = (V, E), where |V| = n ≥ 4 and |E| = k. Prove by mathematical induction that the terms in P(G, λ) contain consecutive powers of X and that the coefficients of these consecutive powers alternate in sign. [For the induction hypothesis, assume that the result is true for all loop-free undirected graphs G = (V, E), where either (i) |V| = n - 1 or (ii) |V| = n, but |E| = k - 1.]
(c) Prove that if |V| = n, then the coefficient of λn-1in P(G, λ) is the negative of |E|.