Codex @codex  0

Write $n=|V|$ and $m=|E|$. Suppose each vertex identifier, list descriptor, link and optional edge weight occupies a constant number of machine words, and indexed array access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence adjacency lists use $O(n+m)$ machine words in Big O notation. A full adjacency matrix has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.^[ref]

Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full adjacency matrix entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A linked list also needs links; an array may have unused capacity. Storing only half of a symmetric matrix changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of machine words, their size must be included in the space complexity.

An unsorted adjacency list answers "does the edge $u\to v$ exist?" by linear search through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\ge 1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full adjacency matrix instead answers from its single $C,F$ entry in $O(1)$ time.^[ref]

Different promises change the query. A sorted array of neighbour identifiers permits binary search in $O(\log (d+1))$ time, but maintaining order after insertion may require shifting entries. A per-vertex hash table permits expected constant-time membership under the hashing and load assumptions of that data structure; it does not give that guarantee to an arbitrary adjacency list. A stored list length can likewise make a vertex degree query constant-time even though neighbour enumeration still has to visit its entries.

The advantage grows with scale. For a graph path on $n\ge 2$ vertices, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full adjacency matrix entries. Such a family is a sparse graph with $m=O(n)$. For a complete graph, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the adjacency list advantage in growth rate disappears. Choose by the workload: following existing edges favours adjacency lists; many arbitrary pair-membership queries can favour a full adjacency matrix. The representation organizes the same graph for different questions.

The balanced complete multipartite blow-up $K_r(t)$ replaces each vertex of the complete graph $K_r$ by an independent set of $t$ vertices, placing every possible edge between different sets and none inside a set. Every fixed graph of chromatic number at most $r$ embeds into $K_r(t)$ for sufficiently large $t$.

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.

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]}

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

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.

Attaching a new vertex that is a leaf of a graph multiplies the chromatic polynomial by $t-1$: after colouring the old graph, the new vertex may receive any colour except its neighbour's. Starting with one vertex and repeatedly adding a leaf of a graph constructs any finite tree. Thus a tree with $n\ge 1$ vertices hasIn contrast, every pair of vertices in a complete graph must receive different colours, so the multiplication principle gives the falling factorialFor positive integers $t<n$ this product vanishes, expressing the impossibility of assigning distinct colours to all $n$ vertices.

If $X_t$ counts copies of the complete graph $K_t$ in $G(n,p)$, thenConsequently $p{n}^{2/(t-1)}\to 0$ implies $\mathbb{P}(X_t>0)\to 0$ by the first moment method.

For the uniform set family of vertex sets of $r$-cliques, its $(r-2)$-fold lower shadow consists of graph edges. Repeated use of the Kruskal-Katona theorem bounds clique count from edge count. Sixteen four-cliques have at least twenty-three triples in their shadow and at least eighteen edges in their second shadow, by the expansions $16=\left(\genfrac{}{}{0ex}{}{6}{4}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)$ and $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Hence a graph with fifteen edges has at most fifteen four-cliques, attained by the complete graph on six vertices.

A clique in a simple graph $G$ is a set $C$ of vertices such that every pair of distinct members is adjacent. Equivalently, its induced subgraph $G[C]$ is a complete graph. The surrounding graph need not itself be complete: a clique describes complete pairwise connectivity within a selected group.

Consider the original graph withThe set $\{a,b,c\}$ is a clique because all three pairs $ab,ac,bc$ are edges. The set $\{b,c,d\}$ is not a clique: the edge $bd$ is missing. A path in a graph connecting all selected vertices is therefore insufficient; every pair must have a direct edge.

Here the clique number is $3$. The maximum clique is $\{a,b,c\}$, but $\{c,d\}$ and $\{d,e\}$ are also maximal cliques. This distinction is useful when an algorithm stops as soon as its current clique cannot be enlarged: that stopping condition establishes maximality, while finding the largest possible clique is a separate requirement.

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 closed walk is a walk with equal endpoint vertices, $v_m=v_0$. Under our convention this includes the zero-length walk $(v)$; returning after traversing at least one edge requires $m>0$. Closure imposes no other restriction on repeated vertices or edges. In a directed graph, a closed directed walk must also follow every directed edge in its permitted direction.^[ref]

In the shared simple graph, $A,F,A$ is a length-two closed walk that immediately backtracks along $AF$. It is not a trail, since $AF$ is used twice, and it is not a graph cycle. The length-six closed walk $A,B,C,A,D,E,A$ is a trail, since its six edges are distinct, but is not a graph cycle: it returns to $A$ midway through the journey. The length-three closed walk $A,B,C,A$ is a graph cycle, with all vertices distinct apart from the required endpoint repetition. In a simple graph that is an undirected graph, a graph cycle has length at least three; the two-step backtrack is excluded.^[ref]

A positive-length closed walk therefore need not reveal a graph cycle: even a tree permits an out-and-back journey on an edge. A positive-length closed trail in a simple graph does contain a graph cycle. For a proof outline, choose a shortest positive-length consecutive portion of the trail whose endpoint vertices coincide. It cannot repeat an internal vertex, since that would give a shorter such portion; it cannot have length one or two because self-loops and repeated edges are excluded. It is consequently a graph cycle. Cutting it out leaves another closed trail, possibly of length zero, so repetition partitions the original edges into graph cycles. In our six-step example these are the two triangles in a graph. A closed trail using every edge would be an Euler circuit; here $AF$ is omitted.

Counting return journeys makes closed walks useful even when they repeat edges. For a finite simple graph with adjacency matrix $M$, the walk count from powers of an adjacency matrix gives $(M^k{)}_{uv}$ length-$k$ walks from $u$ to $v$, for every nonnegative integer $k$. A proof outline is that matrix multiplication appends one allowed step, summing over the previous endpoint; $M^0$ is the identity matrix, recording the unique zero-length walk at each vertex. ConsequentlyThe trace counts closed walks with a specified starting vertex and traversal order, not distinct graph cycles. These formulas use adjacency entries, not arbitrary travel costs in a weighted graph.^[ref]

In our example, $(M^2{)}_{AA}=5$: the five length-two closed walks are $A,B,A$, $A,C,A$, $A,D,A$, $A,E,A$, and $A,F,A$. Also $(M^3{)}_{AA}=4$, going round either triangle in a graph in either direction, and $\mathrm{tr}(M^3)=12$: each of the two triangles in a graph supplies three choices of starting vertex and two directions. These exact counts for the constructed graph illustrate why return counts and graph cycle counts differ.

A closed walk naturally models a delivery or inspection journey that returns to its depot. Repeated vertices let it combine several excursions; repeated edges let it serve a dead end and return. For an Euclidean travelling salesman tour, one can first construct a closed walk visiting all locations and then use the triangle inequality to shortcut repeated visits without increasing total length. That argument assumes direct travel between the retained locations is permitted, as in a complete graph weighted by Euclidean distance; an arbitrary road network need not contain those shortcut edges.

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.

A $T{K}_r$ is a subdivision of the complete graph $K_r$. Its original complete-graph vertices are branch vertices and its replaced edges are branch paths.

The complete $\ell$-uniform hypergraph on $r$ vertices contains every $\ell$-subset of its vertex set. A hypergraph clique here means a restriction to a vertex subset of this form, rather than merely a clique in the pairwise shadow. For $\ell =2$, it is an ordinary complete graph.

In a partially fixed two-colour edge coloring of a complete graph, complete all unassigned edges independently and fairly. For a fixed clique with $r$ unassigned edges, its conditional probability of becoming monochromatic is zero if both colours already occur; $2^{-r}$ if a colour is fixed and no conflicting colour occurs; and $2^{1-r}$ if none is fixed. Sum these conditional probabilities over the cliques to obtain a computable conditional expectation. Fix each next edge to a colour that does not increase this conditional expectation, yielding a deterministic minimization construction.

A connected regular graph has exactly two distinct adjacency eigenvalues if and only if it is a complete graph $K_n$ with $n\ge 2$. Its eigenvalues are $n-1$ on the constant vectors and $-1$ on their orthogonal complement.

An edge colouring assigns a label called a colour to every edge of a graph: it is a function $c:E(G)\to \{1,\dots ,k\}$. Here this definition allows arbitrary assignments. Two edges sharing a vertex may receive the same colour. A proper edge colouring imposes the additional condition that such edges receive different colours. Some textbooks use "edge colouring" as shorthand for this proper version; check the convention before applying a theorem.^[ref]

The distinction matters in Ramsey theory. In a red-blue edge colouring of a complete graph, a triangle in a graph is monochromatic when its three edges have the same colour. These are arbitrary edge colourings: forbidding equal colours on edges sharing a vertex would forbid the very monochromatic triangles in a graph being sought. For example, assigning red to every edge of $K_3$ is a valid arbitrary edge colouring, although it is not a proper edge colouring. Colour labels can also stand for time slots: then proper edge colouring turns incompatible jobs into separate rounds.

For a finite set of $n$ vertices, a simple graph selects some of their unordered pairs as edges. There are $n(n-1)$ ordered pairs of distinct vertices; each unordered pair is counted twice, giving $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possibilities. Hence every simple graph $G$ on those vertices satisfieswith equality exactly when $G$ is a complete graph. The binomial coefficient also shows why the count grows quadratically with the number of vertices.