Color graphs with structural orderings

Try

A greedy coloring assigns each vertex the first color not used by an already colored neighbor. The order can matter: a poor order may use more colors than necessary. Nevertheless, a graph of maximum degree Δ always admits a coloring with at most Δ+1 colors, because no vertex can have more than Δ forbidden colors at its turn. This is a guaranteed bound, not a claim that greedy finds the chromatic number.

Predict

Predict how deleting low-degree vertices improves the bound. A graph is d-degenerate if every nonempty subgraph has a vertex of degree at most d. Repeated deletion creates an order in which each removed vertex had at most d neighbors still present. Coloring in reverse gives at most d already colored neighbors at each step, so d+1 colors suffice even if some original degrees were much larger.

Experiment

Compare degree-based bounds.

Graph	Maximum degree	Degeneracy	Chromatic number
Star with five leaves	5	1	2
Even cycle	2	2	2
Odd cycle	2	2	3

The star demonstrates why maximum degree can be a weak upper bound. The two cycles demonstrate why the same degree and degeneracy values need not determine the exact chromatic number.

Free a colour at the withheld vertex

Vertex v0 is uncoloured. Predict whether your change preserves every edge constraint and frees a colour at v0. A component swap exchanges the selected vertex's colour and the target colour throughout its connected two-colour component in G−v0.

Graph Triangular prism: theorem appliesFive-cycle: odd-cycle exceptionK4: complete-graph exception Repair Recolour one vertexSwap a whole two-colour component Selected vertex v1v2v3v4v5 Target colour 123 Check proposed repair Reset

Maximum degree Δ = 3. Colours: v0: uncoloured; v1: 1; v2: 2; v3: 3; v4: 2; v5: 1.

Exact graph edges

v0–v1, v1–v2, v2–v0, v3–v4, v4–v5, v5–v3, v0–v3, v1–v4, v2–v5. Drawing crossings are not additional vertices.

Worked prism repair and changed-case feedback

Initially v1 has colour 1 and its two remaining neighbours v2 and v4 both have colour 2. Recolour v1 with 3; v0 then sees 3, 2, 3 and can take 1. The two triangles show that three colours are necessary. Swapping the entire 1/2 component containing v1 instead exchanges colours on v1, v2, v4 and v5, so it preserves a proper colouring but does not free a colour at v0. Compare a local recolouring with a valid but unhelpful component swap.

For the five-cycle, removing v0 leaves a path whose endpoints have opposite colours. Swapping the whole 1/2 component merely reverses those colours. An odd cycle cannot be 2-coloured, because alternation returns the wrong colour. In K4 the four pairwise adjacent vertices require four colours. These are genuine lower bounds, unlike failure of one attempted repair.

This finite experiment illustrates recolouring; it is not a general Brooks colouring algorithm. Settings are temporary practice and change no saved progress or scores.

Understand

A proper coloring assigns distinct colors to adjacent vertices. Its minimum number is χ(G). The greedy proof proceeds through any fixed vertex order: among Δ+1 colors, at most Δ appear on earlier neighbors, so at least one remains. The degeneracy version uses the reverse deletion order as described above. Both algorithms produce a verifiable coloring certificate, while a lower bound requires a different argument, such as a clique or an odd-cycle obstruction. A clique of size r needs r distinct colors, but equality between clique number and chromatic number fails in general.

Apply

A k-critical graph is k-chromatic but becomes (k−1)-colorable upon deleting any vertex. Every such graph has minimum degree at least k−1: otherwise color the deletion and extend to the low-degree vertex, contradicting k-chromaticity. This reduction helps isolate difficult coloring configurations. Brooks’ theorem strengthens the maximum-degree bound for connected finite simple graphs: χ≤Δ unless the graph is complete or an odd cycle. The exceptions are necessary, as direct counts show. We now prove the full statement by induction and colour exchanges. No structural ordering lemma is assumed. The proof is optional depth after the experiment; the feasible-colouring and lower-bound distinction above is the essential application skill.

Why a whole two-colour component can be exchanged

Fix a proper colouring and choose colours i and j. Keep precisely the vertices carrying either colour and all edges between them. In any connected component of this induced graph, exchange i and j. Edges inside the component still have different endpoint colours. An edge leaving the component cannot lead to another i- or j-coloured vertex, because that vertex would belong to the same component. Thus every boundary edge remains proper too. Swapping only part of a component has no such guarantee.

Reduce to an impossible unextendable colouring

Induct on the vertex count. A connected graph of maximum degree at most two is a path or a cycle (including the single-vertex and single-edge complete graphs). Paths and even cycles are 2-colourable; odd cycles and complete graphs are the stated exceptions. Now let Δ≥3, and suppose a connected graph G which is neither exception cannot be coloured with Δ colours. We will derive a contradiction.

Choose any vertex v and let H be the graph obtained by deleting v. Every connected component J of H can be coloured with at most Δ colours. To justify this claim, if J is neither complete nor an odd cycle, apply induction: its chromatic number is at most its maximum degree, which is at most Δ. If J is one of the exceptions, it is regular, meaning all its vertices have the same degree r inside J. Connectivity of G guarantees some vertex of J is adjacent to v. That vertex has degree r+1 in G, so r≤Δ−1. The elementary r+1 greedy bound therefore still uses at most Δ colours. Reuse the same palette across components.

For every Δ-colouring of H, v must have exactly Δ neighbours, carrying all Δ colours once each. Otherwise a missing colour extends to v. Write v_i for the unique neighbour carrying colour i. The word “every” is crucial: each recolouring below produces another colouring to which this same restriction applies.

Three rigidity facts forced by nonextension

Connection. For distinct i and j, the two-colour component containing v_i must also contain v_j. Otherwise swap that component: v_i acquires j while v_j keeps j, freeing i at v. Call the common component C(i,j).

Path. C(i,j) must be a simple path with endpoints v_i and v_j. First, v_i has at most Δ−1 neighbours in H. Their colours must all be distinct. If two shared a colour, at most Δ−2 colours would occur among these neighbours, leaving a colour other than i available at v_i. Recolouring v_i would free i at v, a contradiction. Therefore v_i has exactly one neighbour in C(i,j); the same holds for v_j.

Choose a simple path P in C(i,j) between these endpoints. If its component contains anything beyond P, some internal vertex of P has at least three neighbours in the component: this covers a branch leaving P or a chord of P. Starting from v_i, take the first such vertex u. All these three neighbours have the same colour, the opposite of u’s colour within the pair. Since the total degree of u is at most Δ, its neighbours use at most Δ−2 distinct colours. There is consequently an available colour different from its current colour; the opposite colour is already used on its neighbours, so this new colour lies outside the pair. Recolour u. The segment of P before u becomes an entire two-colour component: v_i had degree one there, and all earlier internal vertices had degree two, with no exits. It no longer reaches v_j. This contradicts Connection for the new colouring. Hence no branch or chord exists, proving Path.

Disjoint interiors. For three distinct colours i, j and k, the paths C(i,j) and C(i,k) meet only at v_i. A further common vertex u would have colour i. It is internal to both paths: the other endpoints have colours j and k, and the only neighbour of v with colour i is v_i. It has two distinct neighbours of colour j and two distinct neighbours of colour k. If Δ=3 this is already impossible. Otherwise those four neighbours use only two colours, so all its neighbours use at most Δ−2 colours. Recolour u with an available colour other than i; this colour is neither j nor k. Removing u from the two-colour path C(i,j) disconnects v_i from v_j, again contradicting Connection. Thus the two paths have no other common vertex.

A final exchange contradicts those facts

If all neighbours of v are pairwise adjacent, each has its full Δ neighbours within the set consisting of v and its neighbours. No edge can leave this set. Since G is connected, G is exactly the complete graph on Δ+1 vertices, contrary to our choice. There are therefore two nonadjacent neighbours; name their colours 1 and 2 in a fixed colouring of H. Colour 3 exists because Δ≥3.

The path C(1,2) begins v_1, u, …, v_2. Nonadjacency gives u≠v_2, and u has colour 2. Swap colours 1 and 3 throughout C(1,3). Now v_1 has colour 3, v_3 has colour 1 and v_2 retains colour 2. By Disjoint interiors, C(1,3) met C(1,2) only at v_1. Thus the entire segment from u to v_2 retains its original colours and connects u to v_2 in the new 1/2 component. Meanwhile the edge u–v_1 connects u to the new colour-3 neighbour in the new 2/3 component. By Connection these are the two components joining the new colour-2 neighbour v_2 to the new colour-1 and colour-3 neighbours, respectively.

Consequently those two paths have both v_2 and u in common. They share the colour 2, but u≠v_2. This contradicts Disjoint interiors, applied to the new colouring. The proposed uncolourable G cannot exist. This completes the induction and proves Brooks’ theorem.

This argument follows the mathematical recolouring strategy in Diestel, Graph Theory, Theorem 5.2.4, with the component, degree and induction steps made explicit. MIT 18.211’s Fall 2021 syllabus names Brooks’ theorem in its graph-colouring topic. The finite experiment checks particular proposals; the proof above establishes the general result.

Changed practice: audit the conclusion, then repair a proof

Take a pentagonal prism: vertices a0,…,a4 form a five-cycle, vertices b0,…,b4 form another five-cycle, and each a_i is joined to b_i. Indices wrap around after 4. Determine its chromatic number with an upper and lower certificate. Then explain why the statement “every connected graph is Δ-colourable by exchanging one component” is false in two different ways.

Feedback: changed graph and scope of the proof

Each vertex has degree 3. The graph is connected, is not complete, and is not itself an odd cycle, so Brooks supplies χ≤3. Either five-cycle forces χ≥3. An explicit certificate, in index order, is a=(1,2,1,2,3) and b=(2,3,2,3,1): check all five edges in each ring and all five matching edges. Thus χ=3. The graph contains odd cycles but is not an odd-cycle graph; the exception concerns the whole connected graph.

K4 and a five-cycle disprove the claim without exceptions. Even after restoring the exceptions, the proof does not say any one chosen component exchange succeeds: the prism experiment has proper exchanges that still leave every colour around v0. The argument considers all hypothetical Δ-colourings of a deletion and derives incompatible structural consequences. It is not a guarantee about one arbitrary local move.

For proof revision, suppose someone writes: “C(i,j) contains a branch, so recolour the branching vertex and the endpoints separate.” Locate the missing condition and repair it. Then explain why Disjoint interiors must hold for every colouring, rather than only for the initial one.

Feedback: the first branch and the new colouring

Choose the first vertex of degree at least three along a simple endpoint-to-endpoint path, starting at v_i. Before that vertex, all internal vertices have degree exactly two in the induced two-colour component and v_i has degree one. Recolouring an arbitrary later branch might leave an alternative route around it; recolouring the first branch isolates the preceding segment, because that segment has no exit. The final exchange produces a new colouring, and the contradiction compares its new two-colour paths. Facts proved only for the initial colouring would not justify that last step. In every step also show that the new colour is available among the Δ colours and differs from the current colour.

These written activities are public practice, not extra saved task records or independent mastery evidence.

Continue

In a scheduling application, vertices may be tasks and edges incompatible pairs. A coloring gives feasible time slots, but modeling pairwise conflicts does not capture constraints involving three tasks jointly unless the model is extended. To report optimality, provide a lower-bound certificate matching the color count when one is available. Otherwise report a feasible coloring and the gap between known lower and upper bounds. The later planar lesson proves a stronger five-color result using topology and color exchanges, illustrating why structural assumptions can improve a generic degree bound.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with count colorings with a recurrence.