Unknown

2.2. Division of Polynomials 63

(b) Show that, if G is a graph with exactly n vertices and no connecting

edges, then

Cc(t) = tn.

(c) Show that, if G is a graph with exactly n vertices, any two of which

are connected by an edge, then

CG(t) = t(t - l)(t - 2)... (t - n + 1).

(d) The chromatic function of a graph can be found by adding together

the chromatic functions of related graphs. Let G be a graph containing two

vertices a and b not connected by an edge. From G, form a graph E by

connecting a and b by an edge and a graph F by replacing a and b by a

vertex c (not already in G) which is to be connected to any vertex in G

which joins either a or b. Show that

CC?(t) = CE(t) + Cl+)*

Deduce from this that one can express any chromatic function as the sum

of chromatic functions of the form t(t - 1)... (t - k + 1) corresponding to

graphs every pair of whose points is joined by an edge.

(e) Each of th e f o 11 owing polynomials is the chromatic function of a graph

with four vertices. Determine the graphs:

t4 - 6t3 + lit’ - 6t, t4 - 5t3 + 8t2 - 4t, t4 - 4t3 + 5t2 - 2t,

t4 - 4t3 + 6t2 - 3t, t4 - 3t3 + 3t2 - t, t4 - 2t3 + P, t4 - P, t4.
(f) Consider the graph with vertices A, B, C, D, E, F diagrammed
above. Show that this graph cannot be colored with 0 or 1 colors, but
can be colored with 2 colors in exactly two ways. Show that its chromatic
polynomial is
t(t - l)(t4 - 8t3 + 28t2 - 47t + 31).
(g) What is th e c h romatic polynomial of the graph made up of the ver-
tices and edges of a cube? of each of the other four platonic solids (tetra-
hedron, octahedron, dodecahedron, icosahedron)?

E.20. The Greatest Common Divisor of Two Polynomials. Formu-
late a definition of common divisor of two polynomials. What is meant by
greatest common divisor in this context? There is some ambiguity in what
the greatest common divisor should be; we can remove it by insisting that it
be manic. Devise a Euclidean algorithm analogous to that of Exercise 1.6.1
for determining the greatest common divisor. Will this algorithm lead to a
representation of the form uf + vg (u and v polynomials) for the greatest
common divisor? Is it true that every common divisor divides the greatest
common divisor? Try out your ideas on the pairs:

(a) 2t3 + 9t2 + 8t - 5 and t2 + 5t + 6