- Asked 2/9
- 2072 Asoj · 4+4 marks
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.
| Vertex | v1 | v2 | v3 | v4 | v5 | v6 | v7 |
|---|---|---|---|---|---|---|---|
| Color | 1 | 2 | 1 | 2 | 1 | 2 | 3 |
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.
| Vertex | v1 | v2 | v3 | v4 | v5 |
|---|---|---|---|---|---|
| Color | 1 | 2 | 3 | 4 | 5 |
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.
| Vertex | a | b | c | d | e | f | g | h |
|---|---|---|---|---|---|---|---|---|
| Color | 1 | 2 | 1 | 2 | 2 | 1 | 2 | 1 |
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? | b1 | b2 | b3 | b4 |
|---|---|---|---|---|
| a1 | yes | yes | yes | yes |
| a2 | yes | yes | yes | yes |
| a3 | yes | yes | yes | yes |
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)
Related questions
- Draw W6, K6, Q3, K2,5 and color them · Discrete Structure, chapter 4 · asked 2×
- Draw K3,4 and C5; chromatic numbers · Discrete Structure, chapter 4 · asked 4×
- Graph coloring and chromatic number · Discrete Structure, chapter 4 · asked 3×
- Complete and bipartite graph · Discrete Structure, chapter 4
- Draw K5 and its chromatic number · Discrete Structure, chapter 4 · asked 4×
- Draw K3,4 and its chromatic number · Discrete Structure, chapter 4
- Draw K4,5 and C6; chromatic numbers · Discrete Structure, chapter 4 · asked 4×