Skip to main content

Draw K3,4 and its chromatic number

Short answer

K3,4 is a complete bipartite graph. Assign one color to all three vertices in set A and another color to the four vertices in set B; no adjacent vertices share a color. Thus χ(K3,4) = 2.

Draw the figure for the complete bipartite graph K3,4 and determine its chromatic number.

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →