Vertex colouring: bounds and exact constructions
Objectives and conventions
Check a proper vertex colouring, find a chromatic number with matching lower and upper bounds, recognize bipartite graphs, and distinguish a greedy colouring from an optimum. Prerequisites: graph connectivity, cycles, degrees and basic counting. All graphs here are finite, nonempty, simple and undirected. We colour vertices, not edges. Colour names are labels with no numerical importance except when a stated greedy rule chooses the smallest available label.
A proper vertex colouring assigns a colour to each vertex so adjacent vertices have different colours. Nonadjacent vertices may share a colour, but are not required to. A graph is k-colourable if some proper colouring uses at most k colours. Its chromatic number χ(G) is the minimum such k. Exhibiting a 4-colouring proves χ≤4, not automatically χ=4.
1. Lower bound plus construction proves an exact answer
A clique is a set of pairwise adjacent vertices. A clique of size r needs r different colours, so χ(G)≥r. Write ω(G) for the largest clique size; then ω(G)≤χ(G). The whole complete graph Kₙ requires n colours. A nonempty edgeless graph needs exactly 1, regardless of how many isolated vertices it has.
The clique lower bound can be strict. C₅, a five-vertex cycle, contains an edge but no triangle, so ω=2. Yet it requires 3 colours. Absence of a triangle does not prove that two colours suffice; longer odd cycles matter.
To prove χ(G)=k, provide two parts: a reason fewer than k colours are impossible and an actual valid assignment using k. A failed attempt to 2-colour proves nothing unless the failure rules out all possible 2-colourings, rather than only a poor choice made earlier.
2. Paths, cycles and parity
A path with at least two vertices needs 2 colours: an edge prevents using 1, and alternating the two colours along the path supplies a valid colouring. A cycle Cₙ with n≥3 behaves differently according to parity.
For an even cycle, alternate colours 1,2 around the cycle; the final edge also joins different colours. Thus χ(C₂ₘ)=2. On an odd cycle, alternating two colours makes the last and first vertices equal, violating the closing edge. No alternative two-colour assignment avoids this because each next colour is forced once the first is chosen. Three suffice: alternate 1,2 along the first n−1 vertices and give the last vertex colour 3. Hence χ(C₂ₘ₊₁)=3.
Worked exact example: a graph consists of cycle v1−v2−v3−v4−v5−v1 and an extra hub h adjacent to all five cycle vertices. The rim needs 3 colours. The hub cannot use any rim colour because it touches every rim vertex, so at least 4 are needed. Colour the rim 1,2,1,2,3 and the hub 4; this is valid, proving χ=4. The exact edge description avoids different conventions for naming wheel graphs.
3. Bipartite graphs and odd cycles
A graph is bipartite when its vertices can be partitioned into two independent sets L,R, with every edge between them. Assigning one colour to each side gives a proper colouring with at most 2 colours. If at least one edge exists, exactly 2 are necessary; an edgeless nonempty graph still needs only 1.
A graph is bipartite exactly when it contains no odd cycle. The forward direction follows because walking along an edge switches sides, so returning to the start takes an even number of edges.
For the converse, choose a shortest-path tree rooted in each connected component and classify vertices by even or odd distance from that root. If an edge joined two vertices with the same parity, their tree paths and that edge would form an odd cycle after removing their common initial tree path. Thus absence of odd cycles means every edge joins opposite parities, yielding a bipartition. This argument also explains why disconnected components should be handled separately.
A practical two-colour test propagates opposite colours along edges; a conflicting edge certifies failure. Merely having an even number of vertices is irrelevant: a triangle plus an isolated vertex has four vertices but is not bipartite.
4. Independent sets and another lower bound
An independent set contains no edge between its vertices. Each colour class in a proper colouring is an independent set. If α(G) is the maximum size of an independent set and the graph has n vertices, k colour classes cover at most kα(G) vertices. Therefore χ(G)≥ceil(n/α(G)).
For C₅, α=2: two nonadjacent vertices can be chosen, but any three vertices on a five-cycle include adjacent ones. Thus χ≥ceil(5/2)=3, matching the explicit 3-colouring. The lower-bound formula is not an equality theorem for arbitrary graphs.
Do not confuse independent set with matching. An independent set selects vertices; a matching selects edges without common endpoints. Also, a maximum independent set need not be a colour class in every optimum colouring. The bound only restricts how many vertices any one class can hold.
5. Greedy colouring and the Δ+1 upper bound
Given a vertex order, greedy colouring visits each vertex and assigns the smallest positive colour not already used by its previously coloured neighbors. Future neighbors have not yet received colours, so only earlier ones constrain that step.
If maximum degree is Δ, at most Δ different colours can be forbidden when a vertex is reached. Among labels 1 through Δ+1, at least one remains available. Therefore every simple graph has χ(G)≤Δ+1, and this greedy procedure produces a colouring with at most that many colours. The result need not minimize the number used.
Worked counterexample: take path 1−2−3−4, but process vertices in order 1,4,2,3. Vertex 1 gets colour 1; vertex 4 also gets 1 because they are nonadjacent. Vertex 2 touches coloured vertex 1 and gets 2. Vertex 3 touches vertex 2 of colour 2 and vertex 4 of colour 1, so it gets 3. Greedy used 3, although the path's true chromatic number is 2.
In the natural order 1,2,3,4, greedy gives colours 1,2,1,2. Order affects this algorithm's answer, not the graph's chromatic number. A result obtained by one heuristic is an upper bound; finding no improvement in a few attempted orders does not prove optimality.
6. Disconnected graphs reuse colours
If G has components G₁,…,G_c, then χ(G)=max χ(Gᵢ). Every component needs at least its own optimum, providing the lower bound. For the upper bound, colour each component using the same palette of that maximum size; no edge joins two components, so palette reuse creates no conflict.
For a graph whose components are C₅ and K₄, the answer is max(3,4)=4, not 3+4=7. A disjoint union and a graph formed by adding all cross-edges are different constructions; the latter can prevent colour reuse.
With exactly two named available colours, a bipartite graph with c connected components has 2^c proper assignments: each component's two-colour assignment can be swapped independently. An isolated vertex also contributes two choices. This counts labelled assignments, not the chromatic number, and it does not require both colours to be used globally. If an odd cycle is present, the number of proper assignments using only those two colours is 0.
7. Modelling a conflict graph
Suppose tasks A,B,C must occur in separate time slots whenever they share a resource, and task D conflicts only with C. Model tasks as vertices and conflicts as edges {AB,BC,CA,CD}. A time slot is a colour. The triangle A,B,C forces 3 slots; assigning A=1,B=2,C=3,D=1 achieves 3.
Only model the constraints actually stated. An edge is a pairwise prohibition against equal colours; it does not encode task duration, precedence or room capacity unless the problem supplies another model. A graph-colouring solution can be mathematically correct while an incomplete real scheduling model omits important constraints.
Checklist and remaining scope
Identify vertices, all conflict edges and whether the task asks for one valid colouring, the minimum number, or the number of labelled assignments. For an exact chromatic number, combine a lower bound with a construction. Check odd cycles rather than triangles alone. Treat greedy output as an upper bound and reuse colours across disconnected components. Chromatic polynomials, edge colouring and more advanced colouring theorems require additional lessons; this is not a claim to have completed every colouring question type.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. Graphs are finite, simple and undirected; preserve each stated matching, labeling and coloring convention.
C01. What is the chromatic number of the cycle C₅?
A. 1 B. 2 C. 5 D. 3
Answer: D
A: A graph containing an edge cannot give every vertex one color.
B: Alternating two colors around an odd cycle makes the final edge monochromatic.
C: Giving every vertex a different color is valid but not minimum.
D: Two colors are impossible by odd-cycle parity, while cyclic colors 1,2,1,2,3 give a valid three-coloring.
C02. Take a five-vertex cycle and add one hub adjacent to all five cycle vertices. What is the resulting chromatic number?
A. 3 B. 4 C. 5 D. 6
Answer: B
A: The rim already needs three colors, and the hub cannot use any rim color because it touches every rim vertex.
B: The rim needs three colors; the universal hub needs a fourth. A rim three-coloring plus a new hub color attains four.
C: Five colors are unnecessary: an explicit four-color construction exists.
D: Six distinct colors are valid but wasteful and do not prove a minimum.
C03. On the path 1−2−3−4, greedy coloring uses the smallest positive available color in the order 1,4,2,3. What does it use, and what is χ?
A. Greedy 2; χ=2 B. Greedy 3; χ=3 C. Greedy 3; χ=2 D. Greedy 4; χ=2
Answer: C
A: In this order, vertices 1 and 4 first get color 1; vertex 2 gets 2, forcing vertex 3 to use 3.
B: The greedy result is not always optimal. The path has a two-coloring in its natural order.
C: Colors in processing order are 1,1,2,3, but alternating colors along the path proves χ=2.
D: No step here needs color 4; the last vertex sees colors 1 and 2 and uses 3.
C04. A bipartite graph consists of a three-vertex path and two isolated vertices. With two labeled colors available, how many proper colorings are there? Both colors need not be used in every component.
A. 8 B. 2 C. 4 D. 16
Answer: A
A: There are three connected components. The path has two orientations and each isolated vertex independently has two choices: 2³=8.
B: This counts only the path’s two orientations and ignores choices at isolated vertices.
C: This includes only one independent isolated-vertex choice rather than both.
D: There are three independent component choices, not four; vertex choices within the connected path are forced after its first color.
C05. A graph is the disjoint union of C₅ and K₄. What is its chromatic number?
A. 7 B. 3 C. 2 D. 4
Answer: D
A: Colors can be reused across components because no cross-component edge exists; their chromatic numbers are not added.
B: K₄ has four mutually adjacent vertices and requires four distinct colors.
C: Both the odd cycle and the four-clique rule out two colors.
D: The component lower bounds give at least max(3,4)=4, and reusing a four-color palette across both components attains four.
C06. Which statement is valid for every finite simple undirected graph?
A. Triangle-free always implies bipartite. B. Bipartite is equivalent to having no odd cycle. C. Having an even number of vertices implies bipartite. D. The chromatic number always equals the clique number.
Answer: B
A: C₅ is triangle-free but contains an odd cycle and is not bipartite.
B: A bipartite cycle alternates sides and has even length. Conversely, absence of odd cycles makes root-distance parity a consistent two-part assignment in each component.
C: A triangle plus an isolated vertex has four vertices but still cannot be two-colored.
D: C₅ has clique number 2 and chromatic number 3, so the general relation is only ω≤χ.
Sources and scope
This original lesson develops the matching/colouring portion of Discrete Mathematics in Section 1 of the official GATE 2027 CS syllabus. The syllabus establishes relevance, not a promise of full-subject mastery. The MIT references support graph definitions and theorems; examples, exposition and practice here are original. Further depth is identified in the lesson rather than assumed complete.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in