Skip to main content

Draw C7, K5, Q3, K3,4 and color them

Short answer

C7: odd cycle cannot be 2-colored, needs 3 colors. K5: all vertices adjacent, χ = 5. Q3: bipartite, color by parity, χ = 2. K3,4: one color for each set, χ = 2.

Draw neat and clean graphs of: C7 (a cycle with 7 vertices), K5 (a complete graph with 5 vertices), Q3 (a 3 dimensional hypercube) and K3,4 (complete bipartite graph). Use graph coloring technique to color each of these graphs and state their respective chromatic numbers.

Cycle C₇

C₇ (cycle with 7 vertices): v1..v7 with edges v1v2, ..., v6v7, v7v1.

         v1
       /    \
     v7      v2
     |        |
     v6      v3
       \    /
      v5 -- v4

Coloring: alternate 1, 2 along the path v1..v6; then v7 touches v6 (color 2) and v1 (color 1), so it needs color 3.

Vertexv1v2v3v4v5v6v7
Color1212123

An odd cycle cannot be 2-colored, so χ(C₇) = 3.

Complete graph K₅

K₅ (complete graph on 5 vertices): 5 vertices, every pair joined, so 10 edges and every vertex has degree 4.

          v1
        /  |  \
      v5 --+-- v2        pentagon v1 v2 v3 v4 v5 plus the five
       \ \ | / /         diagonals v1v3, v1v4, v2v4, v2v5, v3v5
        \  \|/  /
         v4 --- v3

Edges: v1v2, v1v3, v1v4, v1v5, v2v3, v2v4, v2v5, v3v4, v3v5, v4v5.

Coloring: all five vertices are mutually adjacent, so no two can share a color.

Vertexv1v2v3v4v5
Color12345

Fewer than 5 colors would give two adjacent vertices the same color. So χ(K₅) = 5.

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): vertex sets A = {a1, a2, a3} and B = {b1, b2, b3, b4}; every vertex of A is joined to every vertex of B, giving 3 × 4 = 12 edges, and there is no edge inside A or inside B.

   a1       a2       a3        set A
   |\ \    /|\ \    / | \
   | \ \  / | \ \  /  |  \    every a is joined
   |  \ \/  |  \ \/   |   \   to every b
   b1   b2      b3        b4   set B

(Each of a1, a2, a3 has 4 lines going to b1, b2, b3, b4.)

Edge present?b1b2b3b4
a1yesyesyesyes
a2yesyesyesyes
a3yesyesyesyes

Coloring: give color 1 to all of A and color 2 to all of B. No edge joins two vertices of the same set, so the coloring is proper. One color is not enough because the graph has edges. So χ(K₃,₄) = 2. (In general χ(K_{m,n}) = 2.)

Summary: χ(C₇) = 3, χ(K₅) = 5, χ(Q₃) = 2, χ(K₃,₄) = 2.

✓ Answer checked by Claude Opus 5.5 (high effort)

All Discrete Structure chapter 4 questions →