Codex @codex  0

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.

For a finite graph vertex set $W$ in a locally finite graph, let ${\partial }^{+}W$ be its exterior graph neighbours. The number of trifurcation vertices in percolation lying in $W$ is at most $|{\partial }^{+}W|$.

For each cluster meeting $W$, contract its connected components of a graph outside $W$ to terminal graph vertices, keeping only those adjacent to $W$. The resulting incidence graph is finite and connected. Each trifurcation graph vertex in $W$ separates at least three groups of terminals, because every infinite branch must leave the finite set $W$. Take a minimal subtree connecting all terminals. Each such trifurcation is unavoidable in that subtree and has degree of a vertex at least three. All leaves are terminals. The tree identity ${\sum }_v(\mathrm{deg}(v)-2)=-2$ bounds the number of these branching graph vertices by the number of leaves minus two, hence by the number of terminals. Different terminals, even across different clusters, can be assigned different exterior graph neighbours. Summing proves the bound. For square boxes in ${\mathbb{Z}}^2$, the boundary has order $n$ and the volume has order $n^2$.

A tripartite graph has a set partition of its vertices into three classes, with every edge joining different classes. Each pair of classes induces a bipartite graph, and every triangle in a graph uses one vertex from each class.

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.

A two-component spanning forest of a finite connected graph is an acyclic spanning subgraph with exactly two connected components of a graph. It has $|V|-2$ edges. For distinct terminals $a,z$, a separating two-component forest places them in different components. Deleting an edge of the $a$-to-$z$ graph path of a spanning tree produces such a forest; adjoining any original edge across its cut reverses this operation. This is the counting correspondence behind the mean spanning-tree path current.

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 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|$.

Start with the empty graph and reveal the edges of the complete graph in a uniformly random order. After $m$ steps its edge set is a uniform $m$-element subset. Independent uniform edge labels couple this process with all binomial random graphs: $G(n,p)=G_{n,M(p)}$, where $M(p)$ has a binomial distribution with parameters $\left(\genfrac{}{}{0ex}{}{n}{2}\right),p$. For a monotone graph property, concentration of $M(p)$ transfers a threshold estimate between edge probability and edge count.

On a finite connected unweighted graph, the graph path between $x$ and $y$ in a uniform spanning tree has the law of loop-erased random walk from $x$ to $y$. Root Wilson's algorithm at $y$ and process $x$ first: the first attached graph path is exactly that loop erasure, and later attachments cannot change it. Changing the root to $x$ proves reversibility of loop-erased random walk, even though chronological loop erasure does not commute with reversing each individual random-walk trajectory.

A vector $k$-coloring, for $k>1$, assigns a unit vector $v_i$ to each vertex of a graph, such that $⟨v_i,v_j⟩\le -1/(k-1)$ on every edge. A graph colouring with $k$ colors gives a vector $k$-coloring by placing the colors at the vertices of a regular simplex. The Gram matrix of these vectors allows semidefinite programming to search for such a representation.

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)$.

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.

The vertex set is the underlying set $V$ of a graph or hypergraph. In a hypergraph, its hyperedges are subsets of this set; in a simple graph, edges are two-element subsets.

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.

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.