Codex @codex  0

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph $G=(V,E)$, its 2-core is the unique maximum by set inclusion induced subgraph $G[S]$ such thatThe empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that $S$ contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let $ab$ denote the edge $\{a,b\}$ and takeThe triangle in a graph $abc$ has a branching tail attached at $c$, and $z$ is an isolated vertex. In alphabetical order the initial degrees of vertices are $(2,2,3,3,2,1,1,0)$. Deleting $f$ turns $e$ into a leaf of a graph; deleting $g$ leaves $d$ with degree of a vertex two; deleting $z$ changes no other degree of a vertex. Now delete $e$, which makes $d$ a leaf of a graph, and finally delete $d$. Exactly the three edges of $abc$ remain: $C_2(G)=G[\{a,b,c\}]$.

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

An alternating path in a matching $M$ is a graph path whose successive edges alternate between membership in $M$ and membership outside $M$. Here graph paths have no repeated vertices. Alternation alone does not make a graph path an augmenting path in a matching: its endpoints must both be unmatched vertices in a matching. For example, relative to $M=\{(2,3),(4,5)\}$ in the six-vertex path graph, $2,3,4,5$ alternates but has matched endpoints; toggling just those three edges loses one selected edge.

An augmenting path in a matching $M$ is a nonempty alternating path in a matching with distinct endpoints that are both unmatched vertices in a matching. Its first and last edges lie outside $M$. Thus it has $k+1$ unselected edges and $k$ selected edges, for some $k\ge 0$. Taking the symmetric differenceremoves the selected edges on $P$ and inserts its unselected edges. Each internal vertex exchanges one selected edge for another; each endpoint gains its first selected edge. All choices away from $P$ stay in place, so $M^{\prime }$ is a matching in a graph with $|M^{\prime }|=|M|+1$.^[ref]

For an explicit repair, let the path graph $P_6$ have vertices $1,2,3,4,5,6$ in that order and start withThe endpoints $1$ and $6$ are initially unmatched vertices in a matching. Along $P$ the edges are outside, inside, outside, inside, outside $M$. Remove $(2,3)$ and $(4,5)$, then add $(1,2),(3,4),(5,6)$ together:This raises the cardinality from two to three and gives a perfect matching. Six vertices allow at most three disjoint pairs, so it is also a maximum cardinality matching. The initial $M$ is already a maximal matching: every unused edge touches a matched vertex. Augmentation succeeds because it can replace earlier choices instead of only adding to them.

One unused edge joining two unmatched vertices in a matching is the shortest possible augmenting path in a matching. Longer augmenting paths in a matching reassign several partners, explaining why a stalled greedy matching need not be optimal. For edge benefits $w_e$, the change in total benefit iswhich need not be positive even though the cardinality increases. A maximum-weight matching therefore needs a different optimality test. In an assignment equality graph an augmenting path in a matching moves toward a perfect matching while preserving zero reduced costs on matched edges; this is the setting used by the Hungarian algorithm.

For observed neighbor win fractions $p_0,\dots ,p_{n-1}\in (0,1)$ on the path graph $0,1,\dots ,n$, the normalized Bradley-Terry model estimate with ${\hat{\theta }}_n=1$ is ${\hat{\theta }}_i={\prod }_{k=i}^{n-1}{p}_k/(1-p_k)$. This is backward propagation of empirical odds along the path. Every edge proportion is fitted exactly, and strict concavity in edge log-ratios proves that this is the unique global maximum.

A branch set of a graph minor is the connected region representing one target vertex. For finite simple graphs $G$ and $H$, a witness to $H\preccurlyeq G$ assigns a nonempty set $B_x\subseteq V(G)$ to each $x\in V(H)$, such that the sets are pairwise disjoint, each induced subgraph $G[B_x]$ is a connected graph, and every $xy\in E(H)$ has a witnessing edge of $G$ between $B_x$ and $B_y$. Extra edges between branch sets of a graph minor are allowed: they can be deleted. Unused vertices are also allowed.^[ref]

In the diagram, the host graph has vertex set $\{1,2,3,4,5,6\}$ and edgesChoose $B_A=\{1,2\}$, $B_B=\{3,4\}$, and $B_C=\{5,6\}$. Their internal edges $12,34,56$ establish connectedness. The edges $23,45,61$ witness $AB,BC,CA$, respectively, so they form a model of the complete graph $K_3$. The additional edge $24$ also joins $B_A$ to $B_B$; it supplies another witness for the same target edge, not a fourth target edge. Contracting $12,34,56$ and merging duplicate edges gives exactly $\{AB,BC,CA\}$.

The same branch sets of a graph minor also witness the path graph $A,B,C$: retain the witnesses $23,45$, and delete $61$ to remove the unwanted $AC$ adjacency. This demonstrates why the definition requires an edge for every target adjacency, without forbidding other adjacencies in the host graph. For a complete graph $K_t$, there are no unwanted pairs: its model consists of $t$ disjoint connected branch sets of a graph minor with an edge between every pair.

To turn a model into an operation sequence, keep a spanning tree inside each $G[B_x]$, keep one witnessing edge for each edge of $H$, and delete all other edges and unused vertices. Contract each chosen spanning tree to one vertex. Disjointness prevents two target vertices from merging; connectedness provides the edge contractions that merge each individual region. Conversely, track the original vertices merged into every surviving vertex during a deletion-and-edge contraction sequence. They form disjoint connected branch sets of a graph minor, and each surviving edge comes from an original edge between its two regions. A list of these regions, their connecting trees, and their witnessing edges therefore gives a directly checkable certificate.

A caterpillar tree is a tree whose non-leaf vertices lie on a single path, called its spine. Equivalently, deleting all degree-one vertices leaves a path, a single vertex, or an empty graph in the smallest cases. A star graph is a caterpillar tree with a one-vertex spine; every path graph is also a caterpillar tree. Trees with branching that persists after deleting the leaves fail the definition. The spine packages a seemingly branching structure into a linear backbone with attached leaves, which simplifies many counting and layout questions.

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

The center of a graph is the set of vertices with minimum graph eccentricity. For a finite connected graph $G$, putHere $d_G$ is shortest-path distance and $\mathrm{rad}G={\min }_{v}e(v)$ is the graph radius. The center solves a facility-placement problem in which the cost is the distance to the farthest vertex.

In a five-vertex path graph, eccentricities are $4,3,2,3,4$, so only the middle vertex is central. In a four-vertex path, the two middle vertices both have eccentricity two. The center of a tree is always a single vertex or a pair of adjacent vertices: repeatedly deleting all leaves exposes its middle. For a general graph the center need not have this form; every vertex of a cycle graph is central.

Minimizing the sum of distances defines a different objective. For example, let $a,b,c,d$ form a path, and attach three additional leaves to $a$. The center is $\{b\}$, but the sum of distances is smallest at $a$. The farthest-distance criterion and the average-distance criterion can therefore select different locations.

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.

For a cycle graph of length $\ell \ge 3$, the chromatic polynomial is $p_{C_{\ell }}(x)=(x-1{)}^{\ell }+(-1{)}^{\ell }(x-1)$. The graph triangle gives the base case $x(x-1)(x-2)$. For $\ell \ge 4$, the deletion-contraction recurrence for the chromatic polynomial gives $p_{C_{\ell }}(x)=x(x-1{)}^{\ell -1}-p_{C_{\ell -1}}(x)$, since deleting an edge leaves a path graph and contracting it gives the shorter cycle graph. Substitution proves the formula by mathematical induction.

Colour refinement repeatedly separates vertices of a graph according to the colours of their neighbours. Its colours are labels for classes of vertices with the same currently visible structure; they are not a proper vertex colouring requiring adjacent vertices to differ. In individualization-refinement graph search, colour refinement reduces ambiguity before the algorithm branches.^[ref]

Let $c_t(v)$ be a vertex's colour after round $t$. One conceptual update assigns a common new colour exactly when both the previous colour and neighbour-colour multiset agree:The encoding must give distinct labels to distinct signatures. Retaining $c_t(v)$ prevents old classes from merging. When no class splits, the resulting partition of a set is an equitable partition: vertices in the same cell have equal numbers of neighbours in every cell.

For an original example, start all vertices of the six-vertex path graph $1-2-3-4-5-6$ with the same colour. The first round separates endpoints $\{1,6\}$ from internal vertices $\{2,3,4,5\}$. The next separates $\{2,5\}$, which each have an endpoint neighbour, from $\{3,4\}$, which do not. The three cellsare then stable. Reflection of the path exchanges the two vertices in each cell, so the remaining pairs are compatible with a genuine graph automorphism.

Colour refinement is invariant under vertex relabeling. To compare two graphs, colour signatures must be encoded consistently across both, for example by refining their disjoint union of graphs with shared initial colour meanings. A different count of vertices in a resulting colour class certifies graph non-isomorphism.

Agreement is weaker than isomorphism. Starting with one colour, both the complete bipartite graph $K_{3,3}$ and the triangular prism graph remain one six-vertex cell because every vertex has three neighbours. Yet the prism has triangles and $K_{3,3}$ has none. This failure motivates individualizing vertices and searching further; stable colour classes are not, in general, proof that all their vertices are related by graph automorphisms.

For a finite undirected graph with $m>0$ edges, the degree-biased probability distribution isChoose an edge uniformly, then choose one of its two endpoint incidences uniformly. A vertex is selected once for each incident edge end, so the handshaking lemma normalizes the probabilities. For the three-vertex path graph, the probabilities are $(1/4,1/2,1/4)$.

In a bipartite graph, choosing only the endpoint in one specified part instead gives $\mathrm{deg}(v)/m$ on that part and zero on the other. This conditional sampling convention differs from the probability distribution on the whole vertex set.

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.

The continuous-time diffusion model on a finite undirected graph uses the Graph Laplacian in the ordinary differential equationAcross each edge, the higher value sends an amount proportional to the difference to the lower value. The two contributions cancel in the sum over vertices, giving conservation of mass:If the entries represent masses, start with nonnegative entries; signed entries can instead describe deviations from a common level. For the three-vertex path graph, the initial vector $x(0)=(1,0,-1{)}^T$ is an eigenvector with eigenvalue one, so the exact solution isMore generally, an eigenvector with eigenvalue $\lambda$ decays by $e^{-\lambda t}$. The spectral theorem for real symmetric matrices supplies an orthonormal basis of these eigenvectors, and the kernel of a graph Laplacian identifies the surviving terms. On a nonempty connected graph,The limiting value is the original arithmetic mean. On a disconnected graph, each connected component of a graph converges to its own original arithmetic mean. The same matrix therefore measures neighbour disagreement, detects disconnected regions and governs relaxation toward agreement.

An equitable partition of a finite graph groups vertices so that any two vertices in one cell have the same number of neighbours in each cell. For a simple graph with cells $C_1,\dots ,C_k$, this means that numbersdo not depend on which $v$ in $C_i$ is selected. Here $N(v)$ denotes the set of neighbours of $v$. These counts form the equitable quotient matrix $B=(b_{ij})$. An equitable partition need not be a proper vertex colouring and need not have cells of equal sizes.^[ref]

An original five-vertex path graph $1-2-3-4-5$ has an equitable partitionEach endpoint has one neighbour in $C_2$; each member of $C_2$ has one neighbour in $C_1$ and one in $C_3$; the middle vertex has two neighbours in $C_2$. Although the graph is undirected, $B$ is not symmetric matrix, because its entries count neighbours per vertex rather than total edges between cells. Counting those edges from both ends gives $|C_i|b_{ij}=|C_j|b_{ji}$.

The counts also compress an exact part of the adjacency matrix. Let $A$ be that matrix and let $S$ have one column per cell, with $S_{vi}=1$ for $v\in C_i$ and zero otherwise. ThenIndeed, $(AS{)}_{vj}$ counts neighbours of $v$ in $C_j$, which is exactly $(SB{)}_{vj}$. Hence $Bz=\lambda z$ implies $A(Sz)=\lambda (Sz)$. Since nonempty disjoint cells make the columns of $S$ linearly independent, $z\ne 0$ gives $Sz\ne 0$: every eigenvalue of $B$ is an eigenvalue of $A$. For the displayed example, these include $0$ and $\pm \sqrt{3}$.

An equitable partition preserves neighbour counts, not all adjacency information. The disjoint union of graphs of a triangle and a four-vertex cycle has an equitable one-cell partition, since every vertex has two neighbours. Nevertheless, no graph automorphism can send a triangle vertex to a four-cycle vertex: their connected components of a graph are not isomorphic. This distinguishes equitable cells from symmetry orbits and explains why colour refinement may leave ambiguity.

For a vertex $v$ of a finite connected graph $G$, its graph eccentricity is the greatest graph distance to any other vertex:The graph radius is the minimum eccentricity and the graph diameter is the maximum. Eccentricity therefore measures the worst travel distance from a chosen starting point, rather than its average travel distance.

In the four-vertex path graph $1-2-3-4$, the eccentricities are $3,2,2,3$. The two middle vertices are best in this worst-case sense; the radius is two and the diameter three. In a star graph with at least two leaves, the central vertex has eccentricity one and every leaf has eccentricity two. For a disconnected graph, distances across components are usually infinite, so a finite-valued eccentricity requires restricting to a component or stating another convention.

Assign a real value $x_i$ to each vertex. The Graph Laplacian quadratic form measures disagreement across edges:This makes the Graph Laplacian a positive semidefinite matrix. The energy is small when neighbours have similar values, even if distant vertices have very different values; it depends on connections rather than where the graph is drawn. In the three-vertex path graph, take $x=(2,0,-1{)}^T$. Thenand the two edges contribute $(2-0{)}^2=4$ and $(0-(-1){)}^2=1$.

For a short proof, expand $x^T(D-A)x$. Each edge contributes $x_i^2+x_j^2$ through the degree matrix and $-2x_i{x}_j$ through the adjacency matrix, yielding $(x_i-x_j{)}^2$. The sum over unordered edges has no factor $1/2$; a sum over all ordered pairs does:Equivalently, let $B$ be an oriented incidence matrix, with one row per edge. Then $Bx$ records endpoint differences and $L=B^{T}B$, independently of the chosen orientations. This translates a local comparison into a global quadratic form and makes its nonnegativity visible.

The graph radius of a finite connected graph $G$ is the least graph eccentricity of any vertex:It is the smallest worst-case travel distance achievable by choosing one starting vertex. The vertices achieving it form the center of a graph.

For the five-vertex path graph, the eccentricities are $4,3,2,3,4$, so the radius is two and the graph diameter is four. Every finite connected graph satisfies $\mathrm{rad}G\le \mathrm{diam}G\le 2\mathrm{rad}G$: choose a central vertex $c$ and apply the triangle inequality $d(u,v)\le d(u,c)+d(c,v)$. In a five-cycle every vertex has eccentricity two, so radius and diameter coincide. A vertex minimizing the sum of distances solves a different optimization problem.

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.

For nonnegative weights on a finite graph, scan edges in nonincreasing weight order, selecting each when it shares no endpoint with an already selected edge. This greedy matching is a factor-two approximation algorithm for maximum-weight matching.

Proof. Charge each optimal edge to itself if selected, and otherwise to an earlier selected edge that blocked it. The receiving edge weighs at least as much. Each selected edge receives at most two charges, since its two endpoints each meet at most one optimal edge. Summing proves the bound. Sorting takes $O(|E|\log |E|)$ time, followed by a scan that records which vertices are used.

The factor is sharp even for strictly positive weights. On a four-vertex path graph with consecutive weights $1,1+\epsilon ,1$, where $0<\epsilon <1$, the greedy matching weighs $1+\epsilon$ and the optimal matching in a graph weighs two. Their ratio tends to two as $\epsilon \downarrow 0$. For infinitely many sizes, use $k$ disjoint copies with $\epsilon =1/k$, $k\ge 2$. This example isolates the obstruction: a locally attractive edge can block two compatible edges.