--- title: "Draw W6, K6, Q3, K2,5 and color them" subject: "Discrete Structure" chapter: 4 key: "semester_4/discrete_structure:draw-w6-k6-q3-k25-coloring" source: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-w6-k6-q3-k25-coloring site: BCT Engineering --- # Draw W6, K6, Q3, K2,5 and color them Discrete Structure · Chapter 4: Graph Theory - Asked in: 2073 Magh, 4+4 marks - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-w6-k6-q3-k25-coloring - Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4 ## Question 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. ## 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. ## Answer #### 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. ```text 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. | Vertex | h | v1 | v2 | v3 | v4 | v5 | v6 | |---|---|---|---|---|---|---|---| | Color | 1 | 2 | 3 | 2 | 3 | 2 | 3 | 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. ```text 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. | Vertex | v1 | v2 | v3 | v4 | v5 | v6 | |---|---|---|---|---|---|---| | Color | 1 | 2 | 3 | 4 | 5 | 6 | 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. ```text 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):** A = {a1, a2}, B = {b1, ..., b5}; each of a1, a2 is joined to all five of b1..b5, giving 10 edges. ```text 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is the wheel W6 built, and how many vertices and edges does it have? A. A cycle C6 plus a hub joined to all rim vertices: 7 vertices, 12 edges B. A cycle C6 plus a hub joined to all rim vertices: 6 vertices, 12 edges C. A cycle C6 plus a hub joined to two rim vertices: 7 vertices, 8 edges D. K6 with one vertex removed: 5 vertices, 10 edges Answer: A. Rim has 6 vertices and 6 edges, hub adds 1 vertex and 6 spokes: 7 vertices, 12 edges. (Key point: Wheel structure) 2. In coloring W6, why does the hub need a color used nowhere else? A. The hub has the smallest degree B. The hub is adjacent to every rim vertex C. The rim is an odd cycle D. The hub lies on no triangle Answer: B. Being adjacent to all rim vertices, the hub cannot share a color with any of them. (Key point: Hub color) 3. What is chi(W6) and why? A. 2, because W6 is bipartite B. 4, because the rim is an odd cycle C. 3, because the even rim needs 2 colors plus 1 for the hub D. 6, because it has 6 rim vertices Answer: C. The even rim C6 uses 2 colors alternately; the hub needs a third. A triangle h, v1, v2 shows 3 is necessary. (Key point: chi(W6)) 4. How does chi change if the wheel has an odd rim? A. It becomes 4 B. It stays 3 C. It becomes 2 D. It becomes 5 Answer: A. An odd cycle needs 3 colors, and the hub needs a fourth. (Key point: Odd rim) 5. What is chi(K6) and why? A. 3, since K6 contains triangles B. 5, since each vertex has degree 5 C. 2, since edges join two vertices D. 6, since all six vertices are mutually adjacent Answer: D. Every pair is adjacent in K6, so all six vertices need different colors. (Key point: chi(K6)) 6. How does the answer 2-color the hypercube Q3? A. By the parity of the number of 1s in a vertex's label B. By the first bit only, ignoring the rest C. By coloring each face a different color D. By giving every vertex a different color Answer: A. Adjacent vertices differ in one bit, so their parities differ; hence 2 colors suffice and chi(Q3) = 2. (Key point: Q3 coloring) 7. What is chi(K2,5) and the coloring used? A. 5; each b vertex gets its own color B. 2; color 1 for a1, a2 and color 2 for b1..b5 C. 7; every vertex is different D. 3; the two a vertices need different colors Answer: B. No edge lies inside either set, so one color per side works, and edges force at least 2. (Key point: K2,5) ## Close variants set in other exams - [Draw C7, K5, Q3, K3,4 and color them](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-c7-k5-q3-k34-coloring) — Discrete Structure, chapter 4, asked 2× ## Related in Discrete Structure - [Graph coloring and chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adefine-graph-coloring-chromatic-number) — Discrete Structure, chapter 4, asked 3× - [Complete and bipartite graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Acomplete-and-bipartite-graph) — Discrete Structure, chapter 4 - [Draw K6 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k6-chromatic-number) — Discrete Structure, chapter 4, asked 4× - [Draw K3,4 and C5; chromatic numbers](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-c5-chromatic) — Discrete Structure, chapter 4, asked 4× - [Draw K4,5 and C6; chromatic numbers](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k45-c6-chromatic) — Discrete Structure, chapter 4, asked 4×