Graph Theory

The chromatic number is the fewest colours that label every vertex so no edge has one colour at both ends. On a conflict graph it is the minimum number of time slots any valid schedule can use.

A cut vertex is a site whose removal, together with its spans, leaves the network in more pieces than before; a bridge is a span whose removal alone does that. Both name single points of failure.

Exactly when every span lies in one connected piece and every site has even degree. Each visit to a site uses one span in and one out, so an odd degree makes a closed route over every span impossible.

The degrees would sum to 7 x 3 = 21, which is odd, but every graph's degree sum equals twice its edge count and so must be even. The plan is impossible for any wiring, not just awkward ones.

A maximal pairing is one no extra pair can be added to; a maximum pairing is one of the largest possible size. Stopping when nothing more fits guarantees only the first, because an early pair can block two later ones.

No. Exactly n-1 links is necessary for a tree but not sufficient: six nodes wired as a triangle plus a separate three-node path also have five links. Add either connectivity or acyclicity and the third property follows.

Because connectivity guarantees at least one path and acyclicity forbids a second: two distinct paths would diverge and rejoin, and that closed region is a cycle. Uniqueness is itself a definition of a tree.

In start-time order a reservation meets only earlier ones still open, and those all contain its start instant, so it takes a new slot only when the overlap grows. The busiest instant is both the unavoidable floor and the count the sweep reaches.

All items can be staffed at once exactly when every set of items is collectively eligible for at least as many distinct engineers as that set has items. That is Hall's condition, and a violating set is the proof of failure.

Greedy gives each vertex the smallest colour none of its already-coloured neighbours holds. A vertex has at most maximum-degree neighbours, so at most that many colours are blocked, and one of the first maximum-degree-plus-one colours is always free.

Because reachability in an undirected graph is an equivalence relation — reflexive, symmetric and transitive — and the classes of an equivalence relation partition the set. So every site lies in exactly one component and no two components overlap.

At most n(n-1)/2, one link per unordered pair of machines. Every machine then reaches degree n-1, so the degree sum is n(n-1), which is twice the link count exactly as the handshake lemma requires.

The new link's endpoints already had exactly one path between them, and the link closes it into a cycle. Any cycle in the result must use the new link, and only one path completes it.

In a clique every job conflicts with every other, so no two may share a slot and k mutually conflicting jobs force k distinct slots. The size of the largest clique is therefore a lower bound on the chromatic number.

Three screens rule plans out: every listed count must be between 0 and one less than the fleet size, and the counts must sum to an even number. Those are necessary only; a recursive reduction decides the rest.

An augmenting path runs between two currently unpaired vertices and alternates unpaired and paired edges. One exists exactly when the pairing is not maximum, and flipping every edge along it enlarges the pairing by exactly one.

A vertex cover needs a distinct vertex for each pair of a matching, so no cover is smaller than the largest matching. Konig's theorem says that on bipartite graphs the two are exactly equal.

Fund the spans that put bridges on cycles, ranked by what each bridge separates. A span only helps if it creates a second route across the cut; clearing every bridge still leaves cut vertices, which is a separate exposure to price.

Tree-ness itself. n-1 links is the floor for reaching everyone, so a tree has no spare route: losing any link splits it in two. Surviving any single loss needs at least n links, hence cycles and duplicates.

No single route can cover every span exactly once. Four odd-degree sites force at least two separate open routes, because each route absorbs only two odd sites — or you repeat spans to pair the odd sites up first.

A crossing-free drawing satisfies Euler's formula V - E + F = 2, and every face needs at least three link-sides while each link borders two faces. Combining the two caps links at 3V - 6, so such diagrams stay sparse.

n to the power n-2, by Cayley's formula: 16 for four nodes, 125 for five, 1296 for six. When only some pairs can be linked, the matrix-tree theorem counts instead, as a cofactor of the graph's Laplacian determinant.

Measure the floor first: the largest mutually conflicting group is a count no colouring can beat. If that floor is what is rising, only deleting conflicts or adding capacity helps; a wide gap above the floor means better colouring is still available.

Surface the constrained set: the group of items whose combined eligibility names too few engineers, with its exact shortfall. That set is a proof rather than an outcome, and it says precisely where cross-training or hiring raises the ceiling.