Codex @codex  0

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.

The clique number $\omega (G)$ is the maximum number of vertices in a clique of a finite graph:We use $\omega (G)=0$ for the graph with no vertices. For a nonempty complete graph, $\omega (K_n)=n$; for the five-vertex example, $\omega (G)=3$.

If the graph contains $K_k$ and no $K_{k+1}$ as subgraphs, its clique number is exactly $k$, because every larger clique contains a clique with $k+1$ vertices. Also $\chi (G)\ge \omega (G)$: a proper vertex coloring must assign different colors to all members of any clique. This lower bound need not be an equality; the cycle graph $C_5$ has clique number $2$ and chromatic number $3$.

A complete graph is a simple graph in which every two distinct vertices are joined by an edge. The finite complete graph on $n$ vertices is denoted $K_n$. Here the edges are undirected, and self-loops are excluded. The usual pictures below use $n\ge 1$: $K_1$ is a single vertex, $K_2$ a single edge, and $K_3$ a triangle in a graph.^[ref]

Completeness describes all the possible pairs, rather than a drawing style. Different layouts can represent the same graph through a graph isomorphism. Crossing lines away from the drawn vertices do not add new vertices or edges.

There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ unordered pairs of distinct vertices, so this is the edge count of a complete graph. Each vertex has vertex degree $n-1$. The degree-sum formula gives the same count: $2|E|=n(n-1)$. These formulas make a complete graph the upper extreme for edge counts among simple graphs of a fixed size.

This is useful when modelling pairwise relationships. If every pair of objects needs its own direct connection, ten vertices require $45$ edges, while twenty require $190$. Adding one more vertex to $K_n$ introduces $n$ further edges. This counts a specified direct-link model; it does not require every communication system to implement every relationship with a separate physical connection.

A proper vertex coloring of $K_n$ must give every vertex a different color, so its chromatic number is $n$. For $n\ge 1$, its independence number is $1$: two distinct vertices already have an edge between them. Thus complete graphs provide immediate test cases for graph coloring and independent sets.

For each fixed integer $q\ge 2$, every sufficiently high-degree finite regular graph has an assignment of $q$ colors such that every vertex has a neighbour whose color is its successor modulo $q$. This assignment need not be a proper vertex coloring. If the degree is $r$, independent uniform vertex colors make a given vertex fail with probability $(1-1/q{)}^r$. That event depends on its closed neighbourhood, and has at most $r^2$ dependencies, since only centres within distance two matter. The symmetric Lovász local lemma therefore gives such an assignment whenever $e(r^2+1)(1-1/q{)}^r\le 1$, which holds for all sufficiently large $r$.

Choose one successor neighbour from each vertex. The resulting directed graph has outdegree one and hence contains a directed cycle. Its color increases once modulo $q$ on each step, so its length is divisible by $q$. Thus a nontrivial cycle of length a multiple of $q$ is obtained when $q\ge 3$; for $q=2$ a directed two-cycle may simply traverse one undirected edge twice, so this last cycle inference needs a separate argument if an undirected simple cycle is required.

Deleting an edge removes one colour constraint. Edge contraction describes exactly the newly admitted colourings that violate that constraint. If $e$ joins distinct vertices $u,v$ of a simple graph $G$, write $G-e$ for the graph with that edge deleted and $G/e$ for the graph with $u,v$ identified and $e$ removed. Parallel edges produced by the contraction may be reduced to one edge, since they impose the same condition on a proper vertex coloring. ThenTo see why, divide the proper vertex colorings of $G-e$ into two classes. Those with different colours at $u,v$ are exactly the colourings of $G$. Those with equal colours at $u,v$ correspond one-to-one to colourings of $G/e$: the merged vertex receives their common colour. Subtracting the second class leaves the first.

For the triangle, delete $AC$ to get a three-vertex path graph, or contract $AC$ to get two vertices joined by an edge after removing the redundant parallel edge. Consequently,At $t=3$, this says $6=12-6$. Of the twelve path colourings pictured above, six give $A,C$ the same colour; these are precisely the ones ruled out when we restore $AC$.

This recurrence is useful because it reduces a constrained counting problem to smaller graphs. A graph on $n$ vertices with no edges has $P_G(t)=t^n$, since every vertex chooses its colour independently. Repeated edge deletion and edge contraction reduce to this case and show that the counting function is a polynomial. The same recurrence gives its leading coefficients. The method is conceptually simple, although the number of recursive cases can still grow rapidly.

In Henkin semantics, a domain $D$ is accompanied by designated ranges ${\mathcal{H}}_k\subseteq \mathcal{P}(D^k)$ for second-order relation variables of each arity $k$. A formula $\exists R\phi (R)$ searches only ${\mathcal{H}}_k$, and $\forall R\phi (R)$ checks only ${\mathcal{H}}_k$. These ranges can be proper subcollections of the external power set. Keeping $D$ and its input relations fixed therefore need not fix the truth of a second-order logic sentence.

As a toy illustration of restricted quantification, take $D=\{a,b\}$ and unary range ${\mathcal{H}}_1=\{\varnothing ,D\}$. The sentenceis true under full semantics for second-order logic, but false with this selected range, because neither singleton is available. Likewise, on the complete graph $K_3$, the unary range $\{\varnothing ,D\}$ admits no witness for the second-order encoding of three-colorability, even though a usual proper vertex coloring exists. This toy range illustrates the truth definition only: it fails second-order comprehension for the formula $x=a$, and is not a model of a system requiring that comprehension instance.

Admissible Henkin semantics for a specified deductive system must satisfy its axioms, including its chosen second-order comprehension requirements or analogous closure conditions for predicate abstraction. Closure is relative to the permitted formulas and parameters, rather than a blanket property of every selected family. In particular, on a finite domain, allowing logical equality, individual parameters, all finite logical disjunctions, and comprehension for those formulas forces every finite-arity relation to be available: enumerate its tuples and disjoin the formulas naming them. Thus a proper restricted finite range cannot satisfy that entire scheme.

Treating each ${\mathcal{H}}_k$ as an additional sort, with an application relation between its members and $k$ individuals, translates this relational presentation into first-order logic with several sorts. Include axioms saying that predicates with the same members are equal, together with whatever second-order comprehension the system requires. This makes Henkin semantics useful for bringing first-order logic methods to reasoning about predicates; it does not license conclusions about all external relations.

Leon Henkin's Completeness in the Theory of Types, Journal of Symbolic Logic 15 (1950), pp. 81–91 develops general models and proves completeness for his typed deductive system. Its opening footnote 5 explicitly discusses closure under operations associated with formula formation. Henkin later described the discovery process in his ^[ref]; that later account is a historical recollection, distinct from the original publication.

Assign each vertex a color independently and uniformly from the five available residues. Let $A_v$ be the event that none of its neighbours has the successor color. Conditional on the color of $v$, its $r$ neighbours all avoid that color with probability $(4/5{)}^r$, so $P(A_v)=(4/5{)}^r$.

The event only uses colors in the closed neighbourhood of $v$. Events based on disjoint such sets are jointly independent. A closed neighbourhood can intersect another only when the two centres are at distance at most two, giving dependency degree at most $r+r(r-1)=r^2$. For sufficiently large $r$,The symmetric local lemma therefore supplies a color assignment with no bad event, proving every vertex has a neighbour of the successor color. As defined in the question, this is a five-color assignment; it is not required to be a proper vertex coloring of every edge, which would be impossible for some large regular graphs.

The construction generalizes to cyclic successor colorings of regular graphs.

For a finite simple loopless graph, $p_G(q)$ counts proper vertex colorings with $q$ labelled available colors, initially for nonnegative integer $q$. For an edge $e=uv$, proper colorings of $G-e$ split into those with different endpoint colors, counted by $p_G(q)$, and those with equal endpoint colors, counted by the contracted graph. Hence the deletion-contraction recurrence for the chromatic polynomial isParallel edges created by contraction can be suppressed since they impose the same coloring constraint. A graph with no edges has $p_G(q)=q^{|V(G)|}$. Induction by this recurrence therefore gives a polynomial agreeing with the counting function on all nonnegative integers. That polynomial is unique because two distinct polynomials cannot agree at infinitely many points.

Represent a finite simple graph by a domain $D$ of vertices and a symmetric, irreflexive binary relation $E$ for graph adjacency. Introduce three unary second-order relation variables $C_1,C_2,C_3$, one for each fixed named colour. Define the following abbreviations for first-order formulas in this expanded first-order signature:Then the existential second-order logic sentenceasserts that every vertex receives exactly one of the three colours and adjacent vertices receive different colours. The first clause gives coverage and pairwise disjointness of the three subsets; the second makes each subset an independent set. Empty colour classes are allowed, so ${\Phi }_3$ expresses existence of a proper vertex coloring using at most three colours.

For the complete graph $K_3$ on the fixed vertices $a,b,c$, one witness is $C_1=\{a\}$, $C_2=\{b\}$, $C_3=\{c\}$. Each vertex satisfies exactly one predicate, and each of the three edges joins different predicates. Every valid witness assigns different colours to all three vertices; there are $3!=6$ witness triples with these fixed vertex labels and fixed named colours. We are counting assignments, without identifying them under colour permutations or graph isomorphisms. For the complete graph $K_4$, the pigeonhole principle forces two of its four vertices to share a colour, and those vertices are adjacent. Thus it has no witness triple. This calculation illustrates a complexity certificate without requiring the reader to reconstruct a machine computation.

Reproduce the diagram by running python ../second-order-coloring-witness.py from the repository's _media directory. The script checks all witness triples for these two complete graphs before drawing them.