Codex @codex  0

For a nonempty finite simple graph $G$, the chromatic number $\chi (G)$ is the least positive integer $k$ for which $G$ has a proper vertex graph coloring with at most $k$ colours. To establish an exact chromatic number, give a colouring using that many colours and explain why fewer cannot suffice. A colouring alone gives only an upper bound.^[ref]

These small graphs show why the chromatic number measures more than the presence of triangles in a graph:

For a cycle graph of even length, alternating two colours closes consistently; for an odd cycle, it does not, and a third colour on the final vertex suffices. More generally, the two-colourability criterion for bipartite graphs says that $\chi (G)\le 2$ exactly when $G$ is a bipartite graph, and the odd-cycle characterization of bipartite graphs identifies the obstruction as an odd cycle. A nonempty graph with no edges has chromatic number one; a bipartite graph with at least one edge has chromatic number exactly two.

In the pairwise-conflict scheduling model of graph coloring, $\chi (G)$ is the least number of interchangeable slots needed. This turns a drawing into an optimization question: how many groups of compatible activities are unavoidable? Greedy coloring constructs a valid grouping quickly, but its number of colours can exceed the chromatic number.

The chromatic polynomial turns a graph coloring problem into a counting problem: how many choices remain when adjacent vertices must have different colours? For a finite simple graph $G$ and a positive integer $t$, $P_G(t)$ is the number of proper vertex colorings using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.

Consider the three-vertex path graph $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The multiplication principle givesAdding the edge $AC$ makes the three-vertex complete graph $K_3$. Now $C$ must avoid both preceding colours, soWith three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.

For a nonempty graph, the chromatic number records only the first positive integer $t$ for which $P_G(t)>0$. The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is $2$, and for the triangle it is $3$. Counting assignments also gives a useful interpretation for scheduling: if adjacent vertices represent tasks that must use different slots, the chromatic polynomial counts the valid assignments to $t$ named slots. Adding a conflict edge can only remove assignments.

The chromatic polynomial also remembers some of the graph's structure. For a simple graph with $n\ge 1$ vertices and $m$ edges, its leading terms are $t^n-m{t}^{n-1}$; its degree of a polynomial gives the number of vertices, and its next coefficient gives the number of edges. It does not determine the graph completely. A four-vertex path graph and a four-vertex star graph are not related by a graph isomorphism, but both are trees and have chromatic polynomial $t(t-1{)}^3$.

The early connection to map colouring appears in George D. Birkhoff's article ^[ref]. For a derivation of the counting recurrence and its leading coefficients, see Paul Johnson's MAS 341 lecture on chromatic polynomials.

In a proper partial graph coloring, let $R_v$ count coloured neighbours and $D_v$ count their distinct colours. The saving $S_v=R_v-D_v$ leaves $K-D_v$ available colours for only $d(v)-R_v$ initially uncoloured neighbours. If the displayed inequality holds at every vertex, ordinary greedy completion succeeds. Each additionally coloured neighbour removes at most one available colour while also reducing the number of uncoloured neighbours by one.

A graph describes objects, called vertices, and pairwise connections, called edges. Its vertex set $V$ tells us what the objects are; $E$ records their connections. The basic abstraction retains graph adjacency while discarding positions, angles and Euclidean distances: moving the dots in a drawing changes none of the edges. A crossing of two drawn lines is not an extra vertex unless explicitly designated as one. Even the labels can change: a graph isomorphism is a relabelling that preserves graph adjacency in both directions.^[ref]

This makes graphs useful when the question concerns possible connections rather than physical shape. For example, model locations by vertices and direct links by edges; a graph path answers whether one location can reach another. Alternatively, let vertices be activities and edges represent conflicts: a graph coloring then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an edge means before applying graph theory.^[ref]

Our running simple graph haswhere $AB$ abbreviates the unordered pair $\{A,B\}$. It consists of two triangles in a graph, $ABC$ and $DEF$, joined by $CD$. The two drawings above have identical graph adjacency, even though their apparent lengths differ. What counts is that $C$ and $D$ are adjacent, whereas $A$ and $F$ are not.

Route questions require precise vocabulary. A walk is a sequence of consecutive adjacent vertices, permitting repetitions; its length counts traversed edges. A trail is a walk that repeats no edge; a graph path repeats no vertex. For a multigraph, the walk must also specify which parallel edge each step uses. For instance, $A,B,A,C,D,F$ is a length-five walk but not a trail, since it uses $AB$ twice. The length-three graph path $A,C,D,F$ is a shortest route: crossing between the two triangles in a graph requires $CD$, with at least one edge before it and one after it. Thus $d(A,F)=3$ in graph distance, regardless of the drawing.^[ref]

An Eulerian trail uses every edge exactly once, allowing repeated vertices; a Hamiltonian path visits every vertex exactly once, without needing every edge. Here $C,A,B,C,D,E,F,D$ is an Eulerian trail of length seven, whereas $A,B,C,D,E,F$ is a Hamiltonian path of length five. The first repeats $C,D$; the second omits $AC,DF$. Calling an Eulerian trail an "Eulerian path" must not be taken to impose our graph path convention.^[ref]

The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by vertices and the seven bridges by distinct edges, giving a multigraph. Their degrees of vertices are $3,3,3,5$. In a trail using every edge, arrivals and departures pair at every internal vertex, so at most the two endpoints can have odd vertex degree. Four odd degrees of vertices therefore rule out such a route. This early foundational example of graph theory needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.^[ref][ref]

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

For a finite simple graph, choose an order of its vertices and process them one at a time. Give each vertex the smallest positive colour label not already used by its coloured neighbours, and keep all earlier assignments. This is greedy coloring: each step makes a locally available choice. The resulting graph coloring is proper because, for each edge, its later endpoint avoids the colour of its earlier endpoint.^[ref]

If the maximum degree of a graph is $\Delta (G)$, a vertex has at most $\Delta (G)$ previously coloured neighbours, forbidding at most that many distinct colours. At least one label among $1,\dots ,\Delta (G)+1$ remains available. Consequently every order givesThis is an upper bound, not a promise that greedy coloring attains the chromatic number.^[ref]

Consider the path graph $P_4$ with edges $12,23,34$. In the order $1,2,3,4$, greedy coloring assigns the colours $1,2,1,2$ respectively. In the order $1,4,2,3$, it assigns colours $1,1,2,3$ in processing order: vertices $1,4$ both get colour $1$, then vertex $2$ gets colour $2$, and finally vertex $3$ sees colours $2$ and $1$ at its two neighbours and must take colour $3$. Written in vertex order $1,2,3,4$, this second colouring is $1,2,3,1$.

The path graph has chromatic number two: the first assignment achieves two colours, and any edge rules out one. Its maximum degree of a graph is two, so three colours in the second assignment still satisfy the bound. The extra colour comes entirely from the processing order. The crown graph gives a larger family where a poor order can make greedy coloring use arbitrarily many colours although the chromatic number remains two.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

In a kernel-perfect directed graph, lists of size at least $d^{+}(v)+1$ admit a proper graph coloring. Choose a color $a$ and a digraph kernel in the subgraph on vertices whose lists contain $a$. Color that kernel $a$, delete it, and remove $a$ from the remaining lists. Every vertex losing a color also loses an outgoing neighbour; hence the inequality persists. Induction on the vertex count finishes the proof.

Throughout this question the binomial random graph has $p=1/2$, as fixed in the introduction. Let $L={\log }_{2}n$ and $s=\lceil 2L\rceil$. Count the $s$-vertex independent sets by a random variable $I_s$. Linearity of expectation givesFor the second inequality, $s\ge 2L$ implies $sL-s(s-1)/2\le s/2\le L+1/2$. For the limit, $s!\ge (s/2{)}^{\lfloor s/2\rfloor }$ grows faster than $n$. By the first moment method, with high probability there is no such independent set; any larger independent set would contain one. Thus the independence number satisfies $\alpha (G)\le s-1<2L$ with high probability.

Every class of a proper graph coloring is an independent set, giving the claimed chromatic lower bound:

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]

A proper vertex coloring assigns labels to the vertices of a graph so that vertices joined by an edge have different labels. Each colour class is an independent set. The chromatic number is the least number of labels needed for this form of graph coloring.

Second-order logic extends first-order logic by allowing existential quantification and universal quantification over second-order relation variables, as well as over individual objects. In the relational presentation used here, an individual variable $x$ ranges over a domain $D$, while a second-order relation variable $R$ of arity $k$ denotes a subset of $D^k$. Unary second-order relation variables denote subsets of $D$; binary ones denote binary relations. Presentations with function variables can instead describe their graphs by second-order relation variables, with first-order formulas requiring a unique output for every input.

For a graph with vertices $D$ and fixed graph adjacency $E$, the first-order sentence $\forall x\exists yE(x,y)$ says that every vertex has a neighbour. It selects individual vertices while $E$ retains its given interpretation. By contrast,selects an entire subset $P$ and says that it is a nonempty independent set. Here $P$ is a unary second-order relation variable, rather than a symbol in the input first-order signature. This particular property also has a simple first-order sentence on simple graphs; the example illustrates the change in what can be selected, rather than proving a separation in expressive power.

The usefulness of second-order logic is that one can describe a whole proposed solution, such as a graph coloring, and then impose local constraints on it. Syntax alone does not specify which proposed relations are available: full semantics for second-order logic permits all external subsets of $D^k$, whereas Henkin semantics supplies designated ranges. The second-order encoding of three-colorability makes this distinction concrete.