Graph colouring, matching and networks

Four sessions need only two time slots

Sessions A and B share a presenter, B and C share equipment, and C and D share a presenter. These are the only conflicts. Put A,C in slot 1 and B,D in slot 2. Every conflicting pair uses different slots; the nonconflicting A,C pair can share one.

Represent sessions by labelled vertices and the conflicts AB, BC, CD by undirected edges. A colour number means a slot, not a physical paint. One slot cannot work because AB is an edge. Our two-slot allocation works, so two is the minimum. An edge is a constraint: it does not say two sessions must be consecutive.

Define the objects before allocating them

Counting, zero and natural numbers prepares the finite inventories; Addition and subtraction prepares the balances; Examples, explanations and counterexamples prepares the difference between a construction and a proof. Graphs and set notation are defined here. First read the session, matching and rerouting examples; return to the parity, Hall and cut proofs after those cases feel concrete.

For colouring and matching, a graph is finite, undirected and simple: labels are distinct, each edge joins different vertices, and no pair is repeated. A neighbour of v shares an edge with v; its degree is the number of neighbours. A path lists distinct vertices with an edge between consecutive entries, and its length counts edges. A one-vertex path has length zero. A cycle has at least three edges and returns to its start without other repeated vertices.

A walk may repeat vertices and edges. A component is a maximal group of mutually reachable vertices; an isolated vertex is a component by itself. Drawing crossings do not create vertices. Line lengths here are not distances, capacities or costs.

A set records distinct objects. The notation x ∈ S means x belongs to S; S ⊆ L means every member of S belongs to L. The number |S| counts its members, and ∅ is the empty set. A partition divides all objects into disjoint groups whose union is the whole set. Empty groups are allowed when we describe a two-part graph.

A colouring proves an upper bound; a constraint proves a lower bound

A proper vertex colouring assigns a colour to every vertex so the endpoints of every edge have different colours. A colour class is the set of vertices with one colour; it is independent, meaning no edge has both endpoints in it. Conversely, partitioning the vertices into independent classes gives a proper colouring.

The chromatic number χ(G) is the smallest number of colours needed. The empty graph has χ = 0 because no vertex needs a colour. A nonempty edgeless graph has χ = 1. For any nonempty n-vertex simple graph, 1 ≤ χ ≤ n: one colour is necessary and giving each vertex its own colour always works.

A clique is a set of vertices with an edge between every pair of distinct members. A clique of size q forces q different colours, so χ ≥ q. A displayed k-colouring proves only χ ≤ k. To prove χ = k, provide both a valid k-colouring and a reason fewer cannot work.

A triangle has a three-vertex clique and a three-colouring, so χ = 3. A five-cycle A,B,C,D,E,A has no triangle: its largest clique has size 2, yet it needs 3 colours. Alternating two colours around five edges forces the last edge to join equal colours. The colouring A:1,B:2,C:1,D:2,E:3 works. The clique lower bound can be strict.

Greedy colouring is safe, but its order can waste a colour

Choose an order of all vertices. At each vertex, assign the smallest positive colour not used by an already coloured neighbour. Every edge is checked when its later endpoint is coloured, so the result is proper. Let Δ be the maximum degree of a nonempty graph. At most Δ colours are forbidden at any step, so one of 1,…,Δ+1 is available. This proves χ ≤ Δ+1 without claiming the greedy result is minimum.

For AB,BC,CD, the order A,B,C,D yields colours 1,2,1,2. The order A,D,B,C yields A:1,D:1,B:2,C:3: C sees colour 2 at B and colour 1 at D. The graph has not changed and its minimum is still 2. The greedy construction used 3 because of its order.

Greedy colouring solves the task of finding some legal allocation quickly. Certifying the minimum requires a matching lower bound or a complete method that rules out every smaller palette. The finite explorer can check all assignments for its small supplied graphs; that small search is not a general fast optimisation promise.

Two parts are possible exactly when no odd cycle exists

A bipartite graph has a partition L,R with every edge joining opposite parts. Colour L with 1 and R with 2 to obtain a proper colouring using at most two colours. Conversely, the classes of a proper colouring using at most two colours give a bipartition. Thus a bipartite graph with an edge has χ = 2, while the empty and edgeless cases keep their earlier values.

In a two-colouring, colours alternate along a cycle. An odd number of edges returns to the starting vertex with the opposite required colour, which is impossible. Therefore a bipartite graph has no odd cycle.

For the converse, choose a root in each component and assign each vertex the parity of the length of a shortest root-to-vertex path: even or odd. These finite shortest paths exist within the component. Suppose an edge uv joins equal parities. Follow a shortest root-to-u path, the edge uv, and the reverse of a shortest root-to-v path. This is a closed walk of odd length because its length is d(u)+1+d(v). It may repeat vertices, so one more argument is needed.

Every odd closed walk in a loopless graph contains an odd simple cycle. Choose an odd closed walk of smallest positive length among the portions obtained by splitting at repeated vertices. An interior repeated vertex splits it into two shorter closed walks; their lengths add to an odd number, so one is odd, contradicting minimality. Without an interior repetition, its length cannot be 1 because loops are excluded, or 2 because it is odd. It is therefore a cycle of odd length at least 3. Consequently our equal-parity edge would give an odd cycle, contrary to the assumption.

Every edge must therefore join opposite parity classes. Doing this in every component gives a bipartition, including isolated vertices. A four-cycle and a star have edges and need 2 colours; a five-cycle needs 3. The general proof covers disconnected graphs as well as the displayed cases.

A matching picks disjoint pairs

A matching M is a set of edges with no shared endpoint. A vertex used by one of those edges is matched; any other vertex is unmatched. A perfect matching covers every vertex. In a bipartite assignment, a matching saturates L when it covers every left vertex, even if some right vertices remain unused.

A maximal matching cannot be enlarged by simply adding another edge. A maximum-cardinality matching has the greatest possible number of edges among all matchings. Maximum implies maximal, since an addable edge would make it larger. The converse fails: on AB,BC,CD, the matching {BC} is maximal because both other edges touch it, but {AB,CD} has size 2.

The objective here is the number of pairs, with no edge weights. Maximising a sum of costs or preferences is a different problem. Similarly, colouring vertices assigns classes to objects, while a matching selects pairs. If edges themselves are assigned colours so incident edges differ, each edge-colour class is a matching; that is edge colouring, not our vertex-colouring task. A three-edge star needs two vertex colours but three edge colours.

An alternating path can replace a blocking choice

An augmenting path for M is a path whose endpoints are unmatched and whose edges alternate outside M, inside M, outside M, continuing until an outside edge at the other endpoint. Its length is odd. Replace its M edges by its outside edges. Every interior vertex loses one chosen edge and gains one, while each endpoint gains one. No other chosen edge touches an unmatched endpoint or an interior vertex’s already matched slot. The new set is a matching with one additional edge.

Starting with {BC}, the path A,B,C,D alternates AB outside, BC inside, CD outside. Flipping it gives {AB,CD}. The improvement required removing an earlier edge before adding two; maximality had checked only a single direct addition.

A matching is maximum exactly when it has no augmenting path. One direction follows from the improvement just proved. For the other, suppose a larger matching M′ exists. Keep edges belonging to exactly one of M,M′; this is their symmetric difference. Each vertex has degree at most two in this kept graph, with at most one incident edge from each matching. Each nontrivial component is a path or cycle whose edges alternate between the two matchings. This follows by starting at a degree-one endpoint, or following a component of degree-two vertices until it closes.

An alternating cycle has equally many edges of each matching. A path has equal counts or one extra edge from one matching. Since M′ is larger overall, at least one path has one extra M′ edge. It begins and ends with M′ edges. Its endpoints are unmatched in M: an M edge there would continue the component; an edge common to both matchings cannot touch an M′ edge without violating matching. That path augments M. This proves the criterion for finite simple graphs, not only bipartite ones.

Starting with an empty matching and repeatedly augmenting must stop: its size increases by one and cannot exceed half the vertex count, rounded down. When no augmenting path remains, the criterion certifies a maximum matching. Finding such paths in general graphs needs care; for a bipartite graph, the directed alternating search in the next proof is enough.

Hall’s condition checks groups, not only individuals

Let a bipartite graph have parts L,R. For S ⊆ L, write N(S) for all right vertices adjacent to at least one member of S. Hall’s condition is |N(S)| ≥ |S| for every subset S of L. If a matching saturates L, its distinct partners for members of S all belong to N(S), proving the condition is necessary. The empty subset has zero neighbours and satisfies 0 ≥ 0.

It is also sufficient for finite graphs. Choose a maximum matching, which exists because there are finitely many edge subsets. Suppose a left vertex u remains unmatched. From u, search along unchosen edges from left to right and chosen edges from right to left. Any reached unmatched right vertex would produce an augmenting path: remove repeated portions from the directed search route, and its alternating path starts and ends unmatched. Maximum size rules this out.

Let S be the reached left vertices and T the reached right vertices. Every neighbour of a vertex in S lies in T. An unchosen edge is traversed forward; if a reached left vertex has a chosen neighbour, that neighbour was already reached along the chosen edge that discovered it. The starting u has no chosen neighbour. Conversely, every reached right vertex is a neighbour of a reached left one. Thus T = N(S).

Every vertex in T is matched, and its chosen partner is reached in S. Every reached left vertex except u was discovered along such a chosen edge, so these partnerships give a one-to-one correspondence between T and S without u. Hence |S| = |T|+1, contradicting Hall’s condition for S. Therefore no left vertex remains unmatched. This proves sufficiency; it does not assume equal part sizes.

For L = {A,B,C}, R = {X,Y,Z}, take AX,AY,BX,CY,CZ. The assignment AY,BX,CZ saturates L. If instead every left vertex is adjacent only to X,Y, every singleton has neighbours, but S = L has |N(S)| = 2 < 3. No full assignment exists even though no individual is isolated.

A directed network allocates quantities

Now edges have directions and capacities. A finite flow network has a distinct source s and sink t, and directed arcs u→v with capacities c(u→v) ≥ 0. Our networks use integer capacities, have no loops, repeated or opposite arcs, no incoming arc to s and no outgoing arc from t. These conventions simplify the records; residual backward moves will not be additional original arcs.

A flow assigns f(u→v) with 0 ≤ f ≤ c to each original arc. At every vertex other than s,t, the sum of incoming flow equals the sum of outgoing flow. This is conservation: an intermediate vertex neither produces nor stores flow. The value |f| is the total leaving s, which equals the total entering t because summing conservation cancels all intermediate transfers. The bars here denote a flow value, not a set size.

Use vertices s,a,b,t and arcs s→a, s→b, a→b, a→t, b→t, all of capacity 1. Sending one unit along s,a,b,t is feasible: a and b each receive and send 1. It has value 1, but a second unit can still be arranged. Arc labels display flow/capacity; their positions and lengths do not measure either number.

A list of numbers within capacities is not automatically a feasible flow. For example, giving s→a flow 1 and every other arc flow 0 leaves an incoming-outgoing imbalance of 1 at a. Always check conservation as well as each separate capacity.

A backward residual move cancels an earlier transfer

For an original arc u→v with flow f and capacity c, a forward residual move u→v has available amount c−f when positive. A backward residual move v→u has available amount f when positive. Taking a backward move means subtracting flow from that original arc. It does not claim material travels on a new original reverse arc.

Choose a simple source-to-sink path of positive residual moves. Let δ be the smallest residual amount on it. Add δ on every forward original arc and subtract δ on every backward one. Each change stays between zero and capacity. At an interior vertex the two residual moves contribute equal added incoming and outgoing net transfer, so conservation remains true; the source sends δ more and the sink receives δ more. Thus the flow value increases by δ.

After the first unit uses s,a,b,t, the original a→b flow is 1. A residual path s,b,a,t has amounts 1,1,1: forward s→b, backward b→a for original a→b, then forward a→t. Its bottleneck is δ = 1. Add to s→b and a→t, and subtract from a→b. The final original flows are s→a:1, s→b:1, a→b:0, a→t:1, b→t:1, with value 2.

If an algorithm looked only for unused forward routes after the first choice, it would miss this improvement. A residual path describes allowed changes to the existing allocation. The complete original flow table, rather than a drawing of reverse arrows alone, checks what was actually cancelled.

An equal flow and cut prove that no improvement remains

A source-sink cut is a partition S,T of all network vertices with s ∈ S and t ∈ T. Its capacity is the sum of capacities of original arcs directed from S to T. Original arcs from T back into S are not added to this capacity. Summing conservation over S cancels internal arcs and gives |f| = outgoing flow across the cut minus incoming flow across it. Because outgoing flow is at most its capacity and incoming flow is nonnegative, |f| ≤ cut capacity for every feasible flow and every such cut.

In the final four-vertex example, |f| = 2 and the cut S = {s} has capacity 1+1 = 2. This bound and feasible allocation prove both a maximum flow of 2 and a minimum cut capacity of 2. An intermediate flow of 1 with the same cut would not prove optimality.

More generally, start with zero flow and repeatedly augment along positive residual paths until none exists. Integer capacities keep all flows and residual amounts integer. Each δ is at least 1, and the flow value cannot exceed the finite sum of capacities leaving s. Thus the procedure terminates after at most that many augmentations. This termination argument is for integer capacities; it is separate from the cut equality below.

At termination, let S be all vertices reachable from s by positive residual moves; t is not reached. Every original arc from S to its complement must be saturated: otherwise its forward residual move would reach another vertex. Every original arc back into S must have zero flow: otherwise its backward residual move would do the same. Therefore the cut identity becomes |f| = its outgoing capacity. The general cut bound then proves that this flow is maximum and this cut minimum. This is the max-flow/min-cut conclusion for the stated finite integer networks.

The reachable set of an intermediate residual network may contain t and is then not a source-sink cut. Use it as an optimality certificate only after no augmenting path remains. A chosen cut can bound any intermediate value, but equality is what certifies success.

Unit capacities turn a flow into distinct assignments

For a bipartite graph, add a source and a sink. Put capacity-1 arcs from s to each left vertex, from a left vertex to each adjacent right vertex, and from each right vertex to t. A matching of size k gives an integer flow of value k by sending 1 along each selected s,left,right,t route.

Conversely, an integer feasible flow uses only 0 or 1 on each arc. The capacity-1 source and sink arcs, together with conservation, allow at most one used left-to-right arc at any left or right vertex. Those used arcs therefore form a matching whose size is the flow value. The integer augmentation procedure supplies such an integer maximum flow, so it finds a maximum-cardinality bipartite matching. A fractional feasible flow alone is not a list of selected pairs.

For A adjacent to X,Y and B adjacent only to X, the assignment AY,BX covers both left vertices. Restrict both to X and the arc X→t limits the flow to 1; the deficient neighbour group explains the same obstruction through Hall’s condition.

These models retain exactly the recorded constraints. Vertex colours represent reusable classes, matchings represent distinct pairs, and flows represent conserved quantities with capacities. Additional durations, preferences, indivisible shipment sizes or time changes need additional assumptions; they are not encoded merely by moving the drawn vertices.

Predict, reveal and inspect the complete record

Change the colouring order, matching, left subset, flow stage or cut. The input record specifies the selected question before reveal. Then compare your prediction with the exact colouring, edge selection, neighbour inventory, original-arc balances or cut table.

A finite search verifies each supplied case and can reject a proposed allocation. The general conclusions above come from their proofs with stated conditions, not from checking only these small diagrams.

Worked examples

Try it yourself

1. Give χ for the empty graph and for three isolated vertices.

   Show the answer and reasoning

   0 and 1, respectively.

   The empty graph has no vertex to colour. A nonempty edgeless graph needs one colour and has no conflict preventing its use everywhere.

2. A five-cycle has largest clique size 2. Does that prove χ = 2?

   Show the answer and reasoning

   No; χ = 3.

   The clique gives only χ ≥ 2. Two colours fail by odd-cycle alternation, and colours 1,2,1,2,3 around the cycle give a proper three-colouring.

3. A star has a centre joined to three leaves. How many vertex colours and edge colours does it need?

   Show the answer and reasoning

   2 vertex colours and 3 edge colours.

   All leaves can share one vertex colour and the centre uses another. All three edges share the centre, so an edge colouring must give each a different colour.

4. A nonempty simple graph has maximum degree 4. What general upper bound follows, and does it prove equality?

   Show the answer and reasoning

   χ ≤ 5; it does not prove χ = 5.

   At each greedy step at most four colours are forbidden by neighbours, leaving one of five available. A smaller palette may still work.

5. Why must a maximum-cardinality matching be maximal?

   Show the answer and reasoning

   An addable edge would increase its size, contradicting maximum size.

   This uses direct addition only to prove one implication. A maximal matching may still be improved by an alternating replacement, as the four-vertex path shows.

6. Why must Hall’s condition include every subset, including ∅ and the whole left part?

   Show the answer and reasoning

   ∅ satisfies 0 ≥ 0; a large group may fail even when every individual has neighbours.

   For three left vertices restricted to two right vertices, singleton tests pass but the whole left set has only two possible distinct partners.

7. On the five capacity-1 arcs s→a,s→b,a→b,a→t,b→t, is the vector 1,0,0,0,0 feasible?

   Show the answer and reasoning

   No.

   Its numbers meet separate capacities, but a receives 1 and sends 0. The conservation condition at this intermediate vertex fails.

8. An original arc u→v has capacity 7 and flow 4. State its positive forward and backward residual amounts.

   Show the answer and reasoning

   Forward u→v:3; backward v→u:4.

   The forward move can add 7−4 = 3. The backward move can cancel at most the 4 already assigned; it is not an original reverse arc.

9. A cut has original arcs of capacities 3 and 4 leaving S, and one arc of capacity 9 entering S. What is its capacity?

   Show the answer and reasoning

   7.

   A directed cut capacity counts only original arcs from S to its complement: 3+4 = 7. Incoming capacity 9 is not added. Incoming actual flow is subtracted in the flow-value identity.

10. A feasible flow has value 5 and some source-sink cut has capacity 5. What does that establish?

    Show the answer and reasoning

    The flow is maximum and the cut is minimum, both with value 5.

    Every feasible flow is bounded above by this cut, while every cut is bounded below by this flow. Equal values certify both optima.

11. Integer capacities leaving s sum to 8. Starting at zero, why can the residual augmentation procedure use at most eight augmentations?

    Show the answer and reasoning

    Each augmentation increases the integer value by at least 1, and no feasible value exceeds 8.

    Positive residual bottlenecks remain integer. The finite capacity bound proves termination separately from the terminal cut proof.

What to carry forward

• A proper colouring is an allocation certificate; its colour count is an upper bound until a lower bound proves it minimum.
• Greedy colouring uses at most Δ+1 colours on a nonempty simple graph, but different vertex orders may use different counts.
• A finite simple graph is bipartite exactly when it has no odd cycle; an edge forces two colours, while empty and edgeless boundaries differ.
• A maximal matching blocks direct additions; a maximum-cardinality matching blocks every augmenting path.
• Hall’s condition checks all left subsets and characterises a matching saturating that part, without requiring equal part sizes.
• Flow feasibility needs conservation as well as capacities. A residual backward move cancels an original transfer.
• For finite integer-capacity networks, augmentation terminates and a terminal residual reachable set gives an equal maximum flow and minimum cut.