Skip to main content

Draw W6, K6, Q3, K2,5 and color them

Short answer

W6: the hub gets one color, the even rim alternates two, so χ = 3. K6: all six vertices mutually adjacent, χ = 6. Q3: bipartite, color by parity of 1s, χ = 2. K2,5: one color for each part, χ = 2.

Draw neat and clean graphs of: W6 (a wheel with 6 peripheral vertices), K6 (a complete graph with 6 vertices), Q3 (a 3 dimensional hypercube) and K2,5 (complete bipartite graph). Use graph coloring technique to color each of these graphs and state their respective chromatic numbers.

Wheel W₆

W₆ (wheel with 6 peripheral vertices): a cycle C₆ on v1..v6 (the rim) plus a hub h joined to all six rim vertices (spokes). It has 7 vertices and 12 edges.

          v1
         /  \
       v6    v2         h in the centre is joined
       |  h  |          to v1, v2, v3, v4, v5, v6
       v5    v3
         \  /
          v4

Coloring: the hub is adjacent to every rim vertex, so it needs a color used nowhere else. The rim is an even cycle and needs two other colors.

Vertexhv1v2v3v4v5v6
Color1232323

At least 3 colors are needed (h, v1, v2 form a triangle) and 3 suffice. χ(W₆) = 3. (A wheel with an odd rim needs 4.)

Complete graph K₆

K₆ (complete graph on 6 vertices): 6 vertices, every pair joined, so 15 edges and every vertex has degree 5.

            v1
          /    \
        v6      v2        hexagon v1..v6 plus all 9 diagonals:
        | \    / |        v1v3 v1v4 v1v5 v2v4 v2v5 v2v6
        |  X  X  |        v3v5 v3v6 v4v6
        v5      v3
          \    /
            v4

Edges: all pairs vi vj with 1 ≤ i < j ≤ 6.

Coloring: each vertex is adjacent to all five others, so six different colors are needed.

Vertexv1v2v3v4v5v6
Color123456

Six colors are enough and fewer cannot work. So χ(K₆) = 6. In general χ(Kₙ) = n.

Hypercube Q₃

Q₃ (3-dimensional hypercube): the vertices are the 8 binary strings of length 3; two are adjacent when they differ in exactly one bit. It has 8 vertices and 12 edges, and is 3-regular.

      e ------- f
     /|        /|
    / |       / |
   a ------- b  |
   |  h -----|- g
   | /       | /
   |/        |/
   d ------- c

Labels: a = 000, b = 100, c = 110, d = 010, e = 001, f = 101, g = 111, h = 011. Edges: ab, bc, cd, da (front square), ef, fg, gh, he (back square), ae, bf, cg, dh.

Coloring: color each vertex by the parity of the number of 1's in its label (Q₃ is bipartite): even parity gets color 1, odd parity gets color 2.

Vertexabcdefgh
Color12122121

Every edge changes one bit, so it joins an even-parity vertex to an odd-parity one. So χ(Q₃) = 2.

Complete bipartite graph K₂,₅

K₂,₅ (complete bipartite graph): A = {a1, a2}, B = {b1, ..., b5}; each of a1, a2 is joined to all five of b1..b5, giving 10 edges.

      a1                 a2
   /  / | \ \         / / | \ \     each a is joined
  b1 b2 b3 b4 b5     b1 b2 b3 b4 b5   to every b

(The same five vertices b1..b5 are shared by a1 and a2.)

Coloring: color 1 for a1, a2; color 2 for b1..b5. χ(K₂,₅) = 2.

Summary: χ(W₆) = 3, χ(K₆) = 6, χ(Q₃) = 2, χ(K₂,₅) = 2.

✓ Answer checked by Claude Opus 5.5 (high effort)

All Discrete Structure chapter 4 questions →