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

Updated 2 Nov 20265 min read
Graph Coloring: Vertex Coloring, Edge Coloring, Chromatic Number and Theorem Bounds

“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

chi

Reason

Edgeless graph on five vertices

1

No adjacent pair must differ.

P4

2

Its two bipartition sets can receive two colours.

C6

2

An even cycle is bipartite.

C5

3

Oddness rules out two; three colours suffice.

K4

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.

Vertex colouring and edge colouring of the same six-vertex graph, both reaching three colours, with chi(G) = 3 and 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

chi

chi'

What separates them

C6

2

2

Both alternate with two colours.

C5

3

3

An odd cycle blocks two in both cases.

K1,4

2

4

Its four edges meet at the centre.

K4

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).

The six-vertex graph beside its line graph L(G): each edge becomes a vertex, and the triangle a-e-f forces three colours.

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 chi=2

C6 has chi=2

Greedy bound

Any simple graph

chi<=Delta+1

Narrows possibilities

Brooks' theorem

Connected, neither complete nor an odd cycle

chi<=Delta

Running graph has chi<=3

Four Colour Theorem

Planar graph

chi<=4

Upper bound only

Vizing's theorem

Simple graph

Delta<=chi'<=Delta+1

Running graph has 3<=chi'<=4

Konig's line-colouring theorem

Bipartite graph

chi'=Delta

K1,4 has chi'=4

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

chi(G)=2

A bipartition or an odd-cycle search

A bipartition proves two colours suffice; an odd cycle proves they do not.

chi(G)=k

A lower-bound witness and an explicit k-colouring

Matching lower and upper bounds prove the exact value.

chi'(G)=Delta(G)

A Delta-edge-colouring checked at every vertex

The construction meets the maximum-degree lower bound.

chi'(G)=Delta(G)+1

Impossibility with Delta colours plus a Delta+1 construction

Vizing narrows the choices but does not choose between them.

A greedy order uses k colours

The complete ordering trace

Only an upper bound, unless a separate lower bound also reaches k.

A planar graph has chi(G)=4

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.

Go deeper with the full courseEngineering Mathematics for GATE Exam

Keep learning

Discussion