Graph theory

A graph property is a class of finite graphs closed under isomorphism. Its labelled order-$n$ slice consists of members on vertex set $[n]$. Closure under taking arbitrary subgraphs and closure under taking only induced subgraphs lead respectively to subgraph-closed graph properties and hereditary graph properties.

All edges of a simple undirected graph have at least one common endpoint. The empty graph is included when there is at least one vertex, and isolated vertices are permitted. This is the star predicate with isolated vertices allowed; a connected star graph is a special case. Its decision-tree depth is the full number $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of edge bits for $n\ge 3$.

For $n\ge 3$, a full star graph requires every nonincident edge to be certified absent, and fixing those bits suffices. Rejection is certified by at most three present edges with empty common intersection; a triangle needs all three. Hence query certificate complexity is $\max \{3,(\genfrac{}{}{0ex}{}{n-1}{2})\}=\Theta (n^2)$ for this property.

For $n\ge 3$, count the empty graph once, all one-edge graphs once, and each larger accepted graph under its unique center. The latter weighted contribution is $n(n-2)$, giving $1-\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n(n-2)$. Its nonzero value proves evasiveness by the alternating-sum criterion for decision-tree evasiveness.

The speed counts the labelled graphs with a given property on vertex set $[n]$. For proper unbounded hereditary graph properties, its base-two logarithm has leading term $(1-1/r)\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, where $r$ is the property's colouring number.

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

This parameter measures the largest completely unrestricted clique-independent partition class contained in the property. It is zero for bounded-order hereditary classes and infinite for all graphs. For proper unbounded classes it is a positive integer; it differs from the degeneracy-based colouring number of an individual graph.

For a proper hereditary graph property with unbounded orders, the colouring number determines the leading labelled speed. The lower bound comes from one contained clique-independent partition class. For the upper bound, forbid one induced graph from each next-size partition type and use the induced regularity template lemma. Its intermediate-pair graph is clique-free, and sparse or almost-complete pairs have negligible entropy. Bounded-order properties have colouring number zero and are outside this formula.

Graphs in $\mathcal{C}(a,b)$ admit a partition into $a$ total classes, of which $b$ are designated cliques and $a-b$ are designated independent sets. Cross edges are arbitrary and empty classes are allowed. Balanced cross-edge choices give quadratic labelled speed coefficient $1-1/a$. Comparing this count with every $(a+1)$-class type shows that the hereditary colouring number of this class is exactly $a$.

Membership is preserved under deleting vertices and edges. This is the decreasing meaning of monotonicity in extremal graph enumeration; it differs from an increasing monotone graph property used for random-graph thresholds. For a proper unbounded class, its least excluded chromatic number determines the leading quadratic logarithm of its labelled speed.

Here $r+1$ is the least chromatic number of an excluded graph, for a proper unbounded subgraph-closed property. All subgraphs of a balanced Turan graph give the lower bound. For the upper bound, a regularity reduced graph is clique-free, so its dense pairs have the Turan theorem edge bound; sparse pairs contribute only small binary entropy and the bounded partition description costs only a linear number of bits.

A choice of direction for each edge of an undirected graph, producing a directed graph.

A finite undirected graph can be oriented with outdegree at least an integer $k\ge 0$ at every vertex if and only if every vertex subset $U$ is incident to at least $k|U|$ distinct edges. The max-flow min-cut theorem and integral max-flow theorem prove sufficiency by assigning distinct edges to vertices through an incidence flow network; each assigned edge is oriented away from that vertex. Necessity follows by counting outgoing edges from $U$.

For two graphs on the same vertex set, their graph intersection retains exactly the edges belonging to both.

The Kneser graph has as vertices the $k$-element subsets of $[n]$, with an edge between two exactly when they are disjoint. A graph colouring of this graph partitions the $k$-sets into intersecting families.

For integers $n\ge 2k\ge 2$, the chromatic number of the Kneser graph is $n-2k+2$. The upper bound colours by the least element among the first $n-2k+1$ elements, with one final colour for all other sets. The Gale hemisphere lemma and the Lusternik-Schnirelmann-Borsuk theorem give the matching lower bound.

A vertex whose deletion increases the number of connected components of a graph. A Hamiltonian graph has no cut vertex: deleting a vertex from a Hamilton cycle leaves a spanning path.

A hypergraph consists of a vertex set $V$ and a family $E$ of subsets of $V$, called hyperedges. Unlike a graph, a hyperedge may contain more than two vertices. A uniform hypergraph restricts all hyperedges to one fixed size.

A polychromatic coloring of a hypergraph assigns $k$ colors to vertices so that every hyperedge contains all $k$ colors. It is stronger than merely requiring each hyperedge to be nonmonochromatic. Independently random colors and the Lovász local lemma can construct such colorings when edges are sufficiently large relative to their overlap degrees.

For finite $S\subset \mathbb{Z}$, use vertices $\mathbb{Z}$ and hyperedges $S+t$. Independent uniform $k$-coloring gives missing-color probability at most $k{e}^{-|S|/k}$, and the dependency graph of events has degree at most $|S|(|S|-1)$. For $k\ge 20$ and $|S|\ge 6k\log k$, the symmetric Lovász local lemma condition holds. The compactness extension of the Lovász local lemma gives a coloring in which every translate contains every color.

Extremal hypergraph theory studies the largest or smallest possible size of a hypergraph under prescribed forbidden-subhypergraph or covering conditions. It generalizes extremal graph theory. The Turán density describes the asymptotic maximum edge proportion for a fixed uniform forbidden hypergraph.

With $r$ balanced cyclically ordered vertex classes and $2\le \ell \le r+1$, include an $\ell$-set if some start has at least $k+1$ vertices in its first $k$ classes for every $1\le k\le \ell -1$. The cycle lemma implies every $(r+1)$-set contains an edge. Its asymptotic density is $((\ell -1)/r{)}^{\ell -1}$; taking the hypergraph complement gives a lower bound for the Turán density of a complete uniform hypergraph.

For a fixed $\ell$-uniform forbidden hypergraph $F$, its Turán density is the limit of $\mathrm{ex}(n,F)/\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$. Averaging over smaller vertex subsets shows these normalized extremal numbers are nonincreasing, so the limit exists. For ordinary graphs, the Erdős-Stone theorem determines it from the chromatic number.

Normalized hypergraph extremal numbers decrease under vertex sampling and converge to Turán density. At a fixed sample size where the extremal density is close to that limit, excess density forces a positive fraction of samples to contain $H$. Counting incidences of copies and samples proves the displayed lower bound. Shrinking $\delta$ also handles the finitely many small orders when the required count is rounded down.

For the complete $\ell$-uniform hypergraph $K_r^{\ell }$, with $r\ge \ell \ge 2$, the bound is $\pi (K_r^{\ell })\le 1-1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. In the complementary covering formulation, every $r$-set containing an edge forces asymptotic edge density at least $1/\left(\genfrac{}{}{0ex}{}{r-1}{\ell -1}\right)$. It follows from clique-extension incidence inequalities and Cauchy-Schwarz inequality estimates on link degrees.

A multihypergraph has a multiset of hyperedges, allowing the same subset of vertices to appear more than once. Its hypergraph vertex degrees and hypergraph codegrees count multiplicity. Such multiplicity is important when several original hyperedges produce the same link in a hypergraph container theorem.

A subset $I$ of the vertices of a hypergraph is independent when no hyperedge lies wholly inside $I$. This generalizes an independent set in an ordinary graph. If a hypergraph has ordinary graph edges as its vertices and forbidden copies as its hyperedges, these independent sets encode graphs without those forbidden copies.

A container family is a collection of vertex subsets such that every hypergraph independent set lies in at least one member. A useful family has few members and each member is small in hypergraph degree measure or induces few hyperedges. Container fingerprints encode the members and permit bounds on the number of independent sets.

For fixed uniformity, sufficiently small nonsingleton hypergraph codegrees relative to $d{\tau }^{|\sigma |-1}$ permit a family of containers whose degree measures are bounded below one by a fixed amount. Each container has a container fingerprint of size $O(\tau n)$. Iteration gives containers inducing at most an arbitrary fixed proportion of all hyperedges, with logarithmic family size $O(n\tau \log (1/\tau ))$. The constants depend on the uniformity and desired edge proportion, and the average degree must be positive.

A container algorithm may use membership in the unknown independent set only through information recorded in its container fingerprint. With a deterministic ordering and deterministic tests, record every positive queried vertex; queried negative vertices can be excluded. All state updates must be recoverable from the fingerprint alone, so replaying the algorithm constructs a container without knowing the independent set.

A container fingerprint is a small vertex subset $T$, usually contained in a hypergraph independent set $I$, which determines a container $C(T)$ containing $I$. A deterministic membership-query algorithm records positive answers in $T$ and uses negative answers to remove vertices from the container. Reconstruction from $T$ follows the golden rule for container algorithms.

The degree of a vertex $u$ in a hypergraph is the number of hyperedges containing $u$. For a uniform hypergraph, summing degrees counts each hyperedge once for each of its vertices, so ${\sum }_u{d}_H(u)=re(H)$. In a multihypergraph, incidences are counted with multiplicity.

For a uniform hypergraph with positive average hypergraph vertex degree $d$, the degree measure is $\mu (S)=(nd{)}^{-1}{\sum }_{u\in S}{d}_H(u)$. It is a probability measure and equals $|S|/n$ in a regular hypergraph. Every hypergraph independent set has degree measure at most $1-1/r$, even when its fraction of all vertices is close to one.

The codegree of a vertex set $\sigma$ in a hypergraph is the number of hyperedges containing every vertex in $\sigma$. For a singleton this is the hypergraph vertex degree; for two vertices it measures how often those vertices occur together. Subset codegrees of all sizes control the overlap relevant to the hypergraph container theorem.

A hypergraph is $r$-uniform if each hyperedge has exactly $r$ vertices. Ordinary simple graphs are 2-uniform hypergraphs. Its average hypergraph vertex degree is $r|E|/|V|$.

Strong regularity refines both the vertex classes and the pair graphs supporting triple hyperedges. The resulting triads in a hypergraph regularity partition have nearly constant relative triple density outside a small exceptional weight. Pair and triple errors must be chosen in a hierarchy strong enough for a relative tetrahedron counting lemma; ordinary graph regularity on the vertex partition alone is insufficient. Refinement raises bounded conditional-density energies.

A triad is the set of triples supported on one prescribed pair cell for each of the three pairs of vertex classes. Relative triple density is measured among those supported triples. In strong hypergraph regularity, the pair cells must themselves be sufficiently regular and have controlled density before a small relative three-dimensional box norm can give a tetrahedron counting lemma.

A sufficiently regular four-partite three-uniform hypergraph, supported on sufficiently regular pair cells of positive density and with positive relative triple densities, has a positive fourth-power number of three-uniform tetrahedra. On complete pair supports, telescoping the four edge functions shows that an error of at most $\xi$ in each three-dimensional box norm gives a counting error at most $4\xi$. The relative version additionally requires control of the pair-support densities.

For each fixed finite uniform hypergraph $F$, having few copies of $F$ forces small edge-edit distance from an $F$-free hypergraph. More precisely, for every $\eta >0$ there is $\rho >0$ such that fewer than $\rho v^{|V(F)|}$ copies can be eliminated by deleting fewer than $\eta v^r$ edges in an $r$-uniform hypergraph. Strong regularity for three-uniform hypergraphs and a relative counting lemma prove the case $r=3$.

For every $\eta >0$, some $\rho >0$ has this property: a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of the three-uniform tetrahedron can be made tetrahedron-free by removing fewer than $\eta v^3$ hyperedges. The four-term progression hypergraph encoding converts this into the length-four case of the Szemerédi theorem.

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.

The three-uniform tetrahedron is the hypergraph on four vertices with all four possible triple hyperedges. It is the complete uniform hypergraph $K_4^3$, and differs from its geometric realization as a tetrahedron. Its edge pattern encodes four-term arithmetic progressions.

The complement of an $\ell$-uniform hypergraph on $V$ has all $\ell$-subsets of $V$ that are not hyperedges of the original hypergraph. An edge in every $r$-set of one hypergraph is equivalent to the absence of a complete $\ell$-uniform $r$-vertex hypergraph in its complement.

A sequence of vertices and edges of a graph, with each edge joining its two consecutive vertices. Vertices and edges may repeat; a path in a graph imposes distinctness conditions. A closed walk ends where it starts.

A walk in a graph whose first and last vertices agree. An Euclidean travelling salesman tour can be estimated by first constructing a closed walk visiting all locations and then using the triangle inequality to shortcut repeated visits.

An undirected graph has edges that are unordered pairs of vertices. In a simple undirected graph there are no loops or multiple edges. The skeleton of a directed graph forgets the directions of its edges and is an undirected graph.

A graph minor is obtained by deleting vertices, deleting edges, and performing edge contractions. Equivalently, its vertices can be represented by disjoint nonempty connected sets of vertices in the original graph, with an edge joining two sets whenever the corresponding vertices are adjacent. These are branch sets of a graph minor.

The complete graph minor density threshold isThe density here is edge count divided by order, half the average degree of a vertex. For large $t$, this threshold has order $t\sqrt{\log t}$, with the logarithm taken to base $e$.

For each positive integer $k$, a nonempty graph satisfying $e(G)\ge 11k|G|$ has a graph minor $H$ satisfyingThe density hypothesis is a lower bound. Reversing its inequality would be false for an edgeless graph. This auxiliary lemma can be used to establish a $7t\sqrt{\log t}$ upper bound for the complete graph minor density threshold.

A branch set is a nonempty set of vertices inducing a connected graph used to represent one vertex of a graph minor. A $K_t$ graph minor is equivalent to $t$ disjoint branch sets with at least one edge between every pair. Connectedness allows each set to be reduced to a single vertex by edge contractions.

In a dense graph with many common neighbours for every pair of vertices, choose disjoint random small sets. A set is good if few vertices have no neighbour in it. The Markov inequality controls the number of bad sets, and random sampling makes almost every pair of good sets adjacent. Add unused common neighbours to connect each set and to repair the remaining missing adjacencies. If the number of used vertices stays below every common-neighbour count, this constructs disjoint branch sets of a graph minor representing a large complete graph.

Contracting an edge $uv$ identifies its endpoints, then removes loops and duplicate edges to produce a simple graph. It reduces the edge count by exactly $1+|N(u)\cap N(v)|$: one for $uv$, and one for each common neighbour.

A vertex cover is a set of vertices meeting every edge of a graph. The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$.

A polynomial-time many-one reduction represents each variable by an adjacent literal pair and each clause by a triangle in a graph. Connect each occurrence vertex to its corresponding literal vertex. A vertex cover of size $n+2m$ must choose one literal vertex per variable and two vertices per clause, and its omitted clause vertex forces a true literal. Conversely a satisfying Boolean valuation supplies such a cover. This establishes NP-hardness of the vertex-cover decision problem from 3-SAT.

The binomial random graph $G(n,p)$ has vertex set $\{1,\dots ,n\}$ and includes each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ possible edges independently with probability $p$.

For a fixed probability strictly between zero and one, the largest independent set has leading size $2{\log }_{1/(1-p)}n$, giving a lower bound for colouring. The matching upper bound uses independent sets in every large subset of a dense random graph, then repeatedly colours and removes such sets. A sufficiently strong probability estimate makes the failure contribution negligible for the expectation.

For fixed $p$ and $\gamma >0$, Janson inequality bounds the failure probability for a given large vertex subset by $\exp (-c|U{|}^2/(\log n{)}^4)$. A union bound over all at most $2^n$ subsets still tends to zero. This uniform statement is essential because vertex sets left by a greedy colouring procedure depend on the graph; one cannot assume each adaptively chosen remainder is an independent fresh random graph.

Group random edges by their larger endpoint. These independent coordinates each change edges incident to only one vertex. Removing that vertex leaves the same graph under any two outcomes, so their chromatic numbers differ by at most one. The McDiarmid inequality with $n$ coordinate ranges of length one gives the displayed concentration bound.

For the binomial random graph $G(n,1/2)$, the chromatic number is $(1+o(1))n/(2{\log }_{2}n)$ with high probability. A first moment method bounds the independence number above. Edge-disjoint clique packing in the complement graph, followed by an edge-exposure martingale and a union bound over moderately large vertex sets, supplies independent sets for greedy colouring by removing independent sets.

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 number $X$ of $k$-cliques in a binomial random graph $G(n,p)$, with $0<p<1$ and $\mu =\mathbb{E}X$,Two $k$-sets overlapping in $j$ vertices share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges. Overlaps of zero or one vertex give independent indicators; $j=k$ includes the diagonal terms. The identity is useful for the second moment method.

If $X$ counts triangles in $G(n,p)$, thenandThus $np\to \infty$ implies $\mathrm{var}X/(\mathbb{E}X{)}^2\to 0$, and the second moment method gives $\mathbb{P}(X>0)\to 1$.

Partition the vertices into two sets of comparable size. If $np\to \infty$, the first set contains a triangle with probability tending to one. Conditional on any triangle chosen using only internal edges, the probability that none of its vertices has a neighbour in the second set is at mostHence $G(n,p)$ contains a triangle with an attached leaf with probability tending to one.

A graph consists of vertices joined by edges.

A graph whose automorphisms act transitively on its vertices: any chosen vertex of a graph can be carried to any other by a symmetry preserving adjacency. Consequently rooted self-avoiding walk counts are independent of the chosen root.

The planar graph with vertices $\{a(1,0)+b(1/2,\sqrt{3}/2):a,b\in \mathbb{Z}\}$ and edges between vertices at Euclidean distance one. Every vertex of a graph has six neighbors. Its site percolation model is a particularly tractable setting for conformal invariance of planar percolation.

Distinct vertices with equal open neighbourhoods are false twins. They are nonadjacent: adjacency would put one vertex in the other's open neighbourhood but not its own. Equal open neighbourhoods define false-twin classes, which are independent sets and have uniform adjacency to every other such class.

A false-twin class is an equivalence class of vertices with identical open neighbourhoods. In edge-triangle symmetrization, merging nonadjacent false-twin classes by cloning the better local score never decreases the objective. A secondary maximization of squared class sizes forces all distinct classes to be adjacent, giving a complete multipartite graph.

The $j$th power of a graph joins distinct vertices whenever their distance in the original graph is at most $j$. For example, the square of a cycle adds edges connecting vertices two steps apart. Graph powers turn constraints on short paths into adjacency constraints.

In a cycle square, each triple of consecutive vertices is a clique. A proper three-colouring therefore repeats with period three and closes exactly when the length is divisible by three. For all other cycle lengths at least four colours are needed; the five-cycle square is a complete five-vertex graph.

A graph cut consists of the edges joining a vertex subset to its complement. In a two-group stochastic block model, crossing and within-group edges have different Bernoulli distributions. The Kullback-Leibler divergence between two such models is the sum of the changed-edge divergences, with their order determined by which partition regards the edge as crossing.

If every graph component has at most $(k+1)n/[k(2k+1)]$ vertices, assigning whole graph components to two sides gives an empty graph cut with the displayed bound. To prove it, maximize the smaller side's weight $S\le n/2$. If $S<kn/(2k+1)$, every component on the larger side has weight at least $n-2S$, because moving a smaller one would improve the smaller side. There are at least $k+1$ such components, since their total exceeds $k$ times the permitted maximum weight. Thus $n-S\ge (k+1)(n-2S)$, a contradiction. The proof also works for arbitrary positive weights.

An oriented incidence matrix records an arbitrarily chosen orientation of each edge of a graph. Use one row per edge, with $+1$ and $-1$ at its endpoints and zeros elsewhere; the transpose convention is also common. The product $D\theta$ records endpoint differences. For a connected graph, $\ker D=\mathrm{span}\{1\}$, since zero difference propagates along every graph path.

For a connected graph, the Moore-Penrose inverse of its oriented incidence matrix satisfies $D^{†}D=I-{\Pi }_1$, because this product is the orthogonal projection onto $(\ker D{)}^{\perp }$. Thus every signal decomposes into its constant mean and $D^{†}D\theta$. Writing $L={\max }_e\Vert (D^{†}{)}_{\cdot ,e}{\Vert }_2$, a sub-Gaussian random vector noise gives a simultaneous bound on $\Vert (D^{†}{)}^{\top }z{\Vert }_{\infty }$ with scale $L\sqrt{\log (m/\delta )}$.

For two graphs $G,H$, their Cartesian product of graphs has graph vertices $(g,h)\in V(G)\times V(H)$. Two graph vertices are adjacent if either their $G$ coordinates agree and their $H$ coordinates are adjacent, or conversely their $H$ coordinates agree and their $G$ coordinates are adjacent. The ladder graph is the product of a graph path with $K_2$.

A ladder graph is the Cartesian product of graphs of a graph path with the two-vertex complete graph $K_2$. Its two parallel rails are joined by a rung at each position. The doubly infinite ladder graph uses an infinite rail indexed by $\mathbb{Z}$.