6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in Kn red and theremaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1)red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors.Assume that r ≥ g. a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9equals the number of blue edges in K9.b) Show that the total number of red and green edges in Kn equals the number of blue edgesin Kn if and only if n = r + g, where g, r are consecutive triangular numbers.[The triangular numbers are defined recursively by t1 = 1, tn+1 = tn + (n + 1), n ≥ 1; sotn = n(n + 1)/2. Hence t1 = 1, t2 = 3, t3 = 6, . . . ]
6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in Kn red and the
remaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1)
red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors.
Assume that r ≥ g.
a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9
equals the number of blue edges in K9.
b) Show that the total number of red and green edges in Kn equals the number of blue edges
in Kn if and only if n = r + g, where g, r are consecutive triangular numbers.
[The triangular numbers are defined recursively by t1 = 1, tn+1 = tn + (n + 1), n ≥ 1; so
tn = n(n + 1)/2. Hence t1 = 1, t2 = 3, t3 = 6, . . . ]
Step by step
Solved in 2 steps with 10 images
