Skip to main content

Draw K3,4 and C5; chromatic numbers

Short answer

K3,4 is a complete bipartite graph with partite sets of sizes 3 and 4. Its chromatic number is 2: assign color 1 to all vertices in one partition and color 2 to the other. C5 is an odd cycle of length 5; its chromatic number is 3 because two colors fail to properly color an odd cycle.

Draw the figure for the complete bipartite graph K3,4 and the cycle graph with 5 vertices (This is usually denoted by C5). What is the chromatic number of the drawn complete bipartite graph K3,4 and the cycle graph C5.

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 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.)

Cycle C₅

C₅ (cycle with 5 vertices): vertices v1..v5 and edges v1v2, v2v3, v3v4, v4v5, v5v1 (5 edges, 2-regular).

        v1
       /  \
     v5    v2
      |    |
     v4 -- v3

Coloring: going around the cycle, colors alternate 1, 2, 1, 2 for v1..v4. Then v5 is adjacent to v4 (color 2) and v1 (color 1), so it needs a third color.

Vertexv1v2v3v4v5
Color12123

Two colors fail because an odd cycle cannot be 2-colored. So χ(C₅) = 3.

Summary: χ(K₃,₄) = 2 and χ(C₅) = 3.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →