Graph Coloring: Vertex Coloring, Edge Coloring, Chromatic Number and Theorem Bounds
Learn to separate vertex coloring from edge coloring, prove exact chromatic values on one six-vertex graph, and apply standard theorem bounds without overclaiming.
KnowledgeGate Team
Exam prep & CS education

“Colour the graph” is incomplete unless you know whether the objects being coloured are vertices or edges. The constraints look similar, but the two optimisation targets are different. For the six-vertex graph, theorem bounds quickly reject impossible values for its chromatic number and chromatic index. Identify the target, prove a lower bound, exhibit a matching colouring, and recognise when a theorem gives only a bound.
Graph coloring vocabulary: what is coloured, and what must differ
A proper vertex colouring is a map c: V -> {1,2,...,k} with c(u) != c(v) for every edge uv. The chromatic number chi(G) is the smallest feasible k, not the result of an arbitrary attempt. All three vertices of K3 are adjacent, so chi(K3)=3.
A proper edge colouring assigns colours to E so that edges sharing an endpoint differ. Its minimum is the chromatic index chi'(G). Every pair of edges in K3 meets, so chi'(K3)=3. The equal values are a coincidence.
Proper colouring is about constraints, not decoration. Non-adjacent vertices and non-incident edges may reuse colours. See Graph Theory for GATE CS: Euler, Coloring, Worked Formulas for the wider topic map, then use GATE CS Exam Preparation to connect the topic to the exam-preparation path.
Chromatic number: lower bounds, upper bounds and exact proofs
Prove lower bound <= chi(G) <= upper bound. A clique of size omega(G) gives chi(G) >= omega(G), while an odd cycle rules out two colours. A proper k-colouring gives chi(G) <= k. Exactness comes when the bounds meet.
Graph |
| Reason |
|---|---|---|
Edgeless graph on five vertices | 1 | No adjacent pair must differ. |
| 2 | Its two bipartition sets can receive two colours. |
| 2 | An even cycle is bipartite. |
| 3 | Oddness rules out two; three colours suffice. |
| 4 | Every pair of vertices is adjacent. |
The greedy bound is chi(G) <= Delta(G)+1, but a greedy run need not be optimal. On P4 with edges {12,23,34}, order 1,2,4,3 gives A,B,A,C: vertex 3 sees both earlier colours. Bipartition {1,3} and {2,4} proves chi(P4)=2.
Worked vertex-colouring example: an odd cycle with one pendant vertex
Let V={1,2,3,4,5,6} and E={12,23,34,45,51,16}. Vertices 1 to 5 form C5; vertex 6 is a leaf at 1. The degrees are d(1)=3, d(2)=d(3)=d(4)=d(5)=2, and d(6)=1, so Delta(G)=3.
Suppose the cycle uses two colours and c(1)=R. Alternation forces c(2)=B, c(3)=R, c(4)=B, and c(5)=R. Edge 51 has R at both ends. Thus chi(G) >= 3.
Assign c(1)=R, c(2)=B, c(3)=R, c(4)=B, c(5)=G, c(6)=B. Check 12: R-B, 23: B-R, 34: R-B, 45: B-G, 51: G-R, and 16: R-B. Hence chi(G) <= 3, so chi(G)=3.

Edge coloring and chromatic index on the same graph
Edges incident on a maximum-degree vertex meet one another, so chi'(G) >= Delta(G). At vertex 1, 12, 51, and 16 force three colours.
Use 12=A, 23=B, 34=A, 45=B, 51=C, 16=B. Incident colours at vertices 1 to 5 are A,C,B; A,B; B,A; A,B; and B,C. Vertex 6 has only B. None repeats, so chi'(G)=3.
Graph |
|
| What separates them |
|---|---|---|---|
| 2 | 2 | Both alternate with two colours. |
| 3 | 3 | An odd cycle blocks two in both cases. |
| 2 | 4 | Its four edges meet at the centre. |
| 4 | 3 | Four mutually adjacent vertices, but three edge matchings. |
Line graphs connect edge coloring back to vertex coloring
In line graph L(G), each edge of G becomes a vertex. Two such vertices are adjacent when the original edges share an endpoint. Thus chi'(G)=chi(L(G)).
Set a=12, b=23, c=34, d=45, e=51, f=16. Then E(L(G))={ab,ae,af,bc,cd,de,ef}. Vertices a,b,c,d,e form a five-cycle; {a,e,f} forms a triangle because those edges meet at vertex 1.
Transfer a=A, b=B, c=A, d=B, e=C, f=B. The triangle needs three colours and the assignment suffices. Therefore chi(L(G))=3=chi'(G).

Coloring theorems: what each result proves and what it does not
Result | Applies when | Conclusion | Use on an exact graph |
|---|---|---|---|
Bipartite criterion | No odd cycle | A graph with an edge has |
|
Greedy bound | Any simple graph |
| Narrows possibilities |
Brooks' theorem | Connected, neither complete nor an odd cycle |
| Running graph has |
Four Colour Theorem | Planar graph |
| Upper bound only |
Vizing's theorem | Simple graph |
| Running graph has |
Konig's line-colouring theorem | Bipartite graph |
|
|
For the running graph, Brooks gives chi<=3 and its C5 gives chi>=3. Vizing gives edge answer 3 or 4, while our construction proves 3. For K1,4, bipartiteness gives chi=2, and Konig gives chi'=Delta=4.
Conditions matter. Brooks excludes complete graphs and odd cycles: K4 has Delta=3, chi=4; C5 has Delta=2, chi=3. Planarity gives only an upper bound. Planar K4, C6, and an edgeless graph need four, two, and one colours.
Graph-coloring claims: choose the certificate before the theorem
Different claims demand different evidence. An odd cycle refutes two-colourability, an explicit colouring supplies an upper bound, and a clique or maximum-degree vertex supplies a lower bound. A greedy trace certifies only what that vertex order used.
Claim to test | Fastest certificate | What the certificate proves |
|---|---|---|
| A bipartition or an odd-cycle search | A bipartition proves two colours suffice; an odd cycle proves they do not. |
| A lower-bound witness and an explicit k-colouring | Matching lower and upper bounds prove the exact value. |
| A Delta-edge-colouring checked at every vertex | The construction meets the maximum-degree lower bound. |
| Impossibility with Delta colours plus a Delta+1 construction | Vizing narrows the choices but does not choose between them. |
A greedy order uses | The complete ordering trace | Only an upper bound, unless a separate lower bound also reaches k. |
A planar graph has | An attempted smaller colouring | The Four Colour Theorem gives at most four, not exactly four. |
Use Graph Coloring MCQs: 10 Solved Questions on Vertex Coloring, Edge Coloring and Chromatic Number for question-by-question GATE practice on bipartite tests, greedy order and planar-graph bounds. The running proof here has a different job: it carries one graph from vertex colouring through edge colouring to chi(L(G))=chi'(G).
Graph coloring: one proof to retain
Three equalities are certified independently on the running graph. The odd cycle and explicit vertex colouring prove chi(G)=3. The degree-three vertex and explicit edge colouring prove chi'(G)=3. The triangle {a,e,f} and transferred colouring prove chi(L(G))=3.
If you want graph colouring placed inside the broader Discrete Mathematics sequence, follow GATE Guidance by Sanchit Sir.
Audit any claimed exact value in two passes: verify the lower-bound witness, then scan every constrained pair in the proposed colouring. A repeated colour invalidates the construction. If the lower and upper bounds do not meet, report the interval instead of an exact chromatic value.
Keep learning
Graph Coloring MCQs: 10 Solved Questions on Vertex Coloring, Edge Coloring and Chromatic Number
Attempt 10 solved GATE questions on graph colouring, from bipartite tests to edge colouring. Each solution proves a lower bound, constructs a colouring or traces the relevant algorithm.
Planar Graphs MCQs: 12 Solved Questions on Kuratowski’s Theorem, Homeomorphism and Edge Bounds
Solve 12 planar graph questions, then check each answer through a forbidden-subdivision argument, a crossing-free redraw, or a short calculation.
Cut Set and Connectivity in Graph Theory: Edge and Vertex Connectivity with Worked Examples
Learn how to calculate edge and vertex connectivity without confusing cuts, degrees, or disjoint paths. The bow-tie graph shows why lambda(G) can exceed kappa(G).
Euler Formula for Planar Graphs: Face Counts, Edge Bounds, and Non-Planarity Tests
Learn how to count faces correctly, extend Euler's relation to disconnected plane graphs, derive edge bounds, and use those bounds without reversing their logic.





