--- title: "Draw K3,4 and C5; chromatic numbers" subject: "Discrete Structure" chapter: 4 key: "semester_4/discrete_structure:draw-k34-c5-chromatic" source: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-k34-c5-chromatic site: BCT Engineering --- # Draw K3,4 and C5; chromatic numbers Discrete Structure · Chapter 4: Graph Theory - Asked in: 2068 Bhadra, 2+2+2+2 marks - Video: [Chromatic number of a Graph in Discrete Mathematics || 5 Solved Examples || DMS || GATE](https://www.youtube.com/watch?v=2KFVnXwbKcs) — Sudhakar Atchala - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-k34-c5-chromatic - Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4 ## Question 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. ## 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. ## Answer #### 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. ```text 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.) #### Cycle C₅ **C₅ (cycle with 5 vertices):** vertices v1..v5 and edges v1v2, v2v3, v3v4, v4v5, v5v1 (5 edges, 2-regular). ```text 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. | Vertex | v1 | v2 | v3 | v4 | v5 | |---|---|---|---|---|---| | Color | 1 | 2 | 1 | 2 | 3 | Two colors fail because an odd cycle cannot be 2-colored. So **χ(C₅) = 3**. **Summary:** χ(K₃,₄) = 2 and χ(C₅) = 3. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is chi(K3,4) and why? A. 2; the two vertex sets each take one color B. 3; the larger set needs a third color C. 4; B has four vertices D. 7; all vertices are different Answer: A. Edges only join A to B, so one color per side works. (Key point: chi(K3,4)) 2. How many edges does C5 have, and what is its degree pattern? A. 4 edges, degrees 1 and 2 B. 10 edges, 4-regular C. 5 edges, 2-regular D. 6 edges, 3-regular Answer: C. A cycle on 5 vertices has 5 edges and every vertex has degree 2. (Key point: C5 structure) 3. When coloring C5 as 1, 2, 1, 2 for v1..v4, why is v5 a problem? A. v5 has degree 4 B. v5 is adjacent to v4 (2) and v1 (1), so needs a third color C. v5 is not connected to v1 D. v5 must repeat color 1 for v3 Answer: B. The odd length makes the alternation clash where the cycle closes. (Key point: Alternating fails) 4. What is chi(C5)? A. 2 B. 4 C. 5 D. 3 Answer: D. An odd cycle cannot be 2-colored, but 3 colors suffice. (Key point: chi(C5)) ## Close variants set in other exams - [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× - [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 K5 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k5-chromatic-number) — Discrete Structure, chapter 4, asked 4× ## Related in Discrete Structure - [Draw K3,4 and its chromatic number](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-k34-chromatic-number) — Discrete Structure, chapter 4 - [Complete and bipartite graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Acomplete-and-bipartite-graph) — Discrete Structure, chapter 4 - [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× - [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× - [Define bipartite graph with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adefine-bipartite-graph-example) — Discrete Structure, chapter 4, asked 2× - [Handshaking theorem; even number of odd vertices](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahandshaking-even-odd-degree-proof) — Discrete Structure, chapter 4, asked 3×