--- title: "Draw C7, K5, Q3, K3,4 and color them" subject: "Discrete Structure" chapter: 4 key: "semester_4/discrete_structure:draw-c7-k5-q3-k34-coloring" source: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-c7-k5-q3-k34-coloring site: BCT Engineering --- # Draw C7, K5, Q3, K3,4 and color them Discrete Structure · Chapter 4: Graph Theory - Asked in: 2072 Asoj, 4+4 marks - Video: [Graph Theory | Graph Coloring & Chromatic Number of Graph | Discrete Mathematics by GP Sir](https://www.youtube.com/watch?v=HKRFK8W5JlE) — Dr.Gajendra Purohit - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/discrete_structure/draw-c7-k5-q3-k34-coloring - Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4 ## Question 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. ## 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. ## Answer #### Cycle C₇ **C₇ (cycle with 7 vertices):** v1..v7 with edges v1v2, ..., v6v7, v7v1. ```text 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. ```text 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. ```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):** 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. ```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.) **Summary:** χ(C₇) = 3, χ(K₅) = 5, χ(Q₃) = 2, χ(K₃,₄) = 2. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In coloring C7 by alternating 1, 2 along v1..v6, what does v7 need and why? A. Color 1, since it is last B. Color 2, since it follows v6 C. Color 3, since it touches v6 (color 2) and v1 (color 1) D. Color 4, since it has degree 2 Answer: C. v7 is adjacent to v6 (2) and v1 (1), so neither 1 nor 2 is allowed. (Key point: C7 coloring) 2. What is chi(C7), and what is the reason? A. 2, because every cycle is bipartite B. 3, because an odd cycle cannot be 2-colored C. 7, because it has 7 vertices D. 4, because it has an odd number of edges Answer: B. Odd cycles are not bipartite, so need 3 colors; 3 suffice. (Key point: Odd cycle rule) 3. What is chi(K5) in this answer? A. 3 B. 4 C. 2 D. 5 Answer: D. All 5 vertices are mutually adjacent, so 5 different colors. (Key point: K5 value) 4. Why is chi(Q3) = 2? A. It has only 8 vertices B. It is a complete graph C. Each edge changes one bit, so it joins an even-parity vertex to an odd-parity one D. Each vertex has degree 2 Answer: C. Parity of 1s splits the vertices into two classes with no edges inside a class. (Key point: Q3 bipartite) 5. How many edges does K3,4 have? A. 7 B. 12 C. 6 D. 21 Answer: B. Each of the 3 vertices in A is joined to all 4 in B: 3 x 4 = 12. (Key point: K3,4 edges) 6. How is K3,4 properly colored, and what is chi? A. Color 1 for all of A and 2 for all of B; chi = 2 B. Three colors, one per vertex of A; chi = 3 C. Four colors, one per vertex of B; chi = 4 D. Seven colors; chi = 7 Answer: A. No edges inside A or inside B, so two colors suffice; edges exist so one color is not enough. (Key point: K3,4 coloring) ## Close variants set in other exams - [Draw W6, K6, Q3, K2,5 and color them](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Adraw-w6-k6-q3-k25-coloring) — Discrete Structure, chapter 4, asked 2× ## Related in Discrete Structure - [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× - [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 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× - [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 - [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×