Graph

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

The doubly infinite ladder graph has graph vertices $\mathbb{Z}\times \{0,1\}$, horizontal edges $\{(j,s),(j+1,s)\}$, and vertical edges $\{(j,0),(j,1)\}$.

The cubic lattice in dimension $d$ has graph vertex set ${\mathbb{Z}}^d$ and an edge between $x,y$ exactly when ${\sum }_i|x_i-y_i|=1$. For $d=2$ it is the square lattice. Every graph vertex has $2d$ graph neighbours, so it is a locally finite graph.

For the nearest-neighbour graph on ${\mathbb{Z}}^d$, a box $B_n=[-n,n{]}^d\cap {\mathbb{Z}}^d$ has $(2n+1{)}^d$ graph vertices and outer graph vertex boundary of size $2d(2n+1{)}^{d-1}$. Thus $|{\partial }^{+}{B}_n|/|B_n|\to 0$. This boundary-to-volume property is the geometric mechanism that contradicts a positive volume density of trifurcation points in the uniqueness proof. It realizes the boundary-growth property of the translation amenable group on the lattice.

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 blow-up replaces each vertex of a graph by an independent set, and each original edge by all edges between the corresponding two sets. Replacing every vertex of $K_r$ by $t$ vertices gives the balanced complete multipartite blow-up $K_r(t)$.

A family of positively many $s$-cliques forces a logarithmic balanced graph blow-up, which can also contain a matching of that many members of the family. To induct on $s$, prune faces with few extensions, apply induction to the remaining $(s-1)$-faces, and use a matching of those faces as one side of a bipartite incidence graph. The common neighbourhood from bipartite density estimate selects logarithmically many disjoint faces with polynomially many common extension vertices.

Cloning a vertex replaces it by several nonadjacent vertices with identical neighbourhoods. In homomorphism density, conditioning on the images of all other vertices reduces cloning to the inequality $\mathbb{E}{p}^t\ge (\mathbb{E}p{)}^t$ from the Jensen inequality. Iterated cloning shows that positive clique homomorphism density forces any fixed complete multipartite blow-up.

A graph is $r$-partite when its vertices can be partitioned into $r$ classes, each an independent set. Edges may be missing between different classes. If all possible edges between different classes occur, it is a complete multipartite graph.

A vertex $v$ is reachable from $u$ if a finite path leads from $u$ to $v$, respecting edge directions in a directed graph. For a finite graph, graph search decides reachability by maintaining the set of discovered vertices; every step discovers a new vertex or examines an edge, so the procedure terminates.

A graph search explores vertices through incident edges while recording visited vertices. On a finite graph, depth-first or breadth-first exploration terminates and decides reachability; recording predecessors also gives a path. Restricting to vertices reachable from a start and able to reach an accepting vertex identifies the productive part of a deterministic finite automaton.

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\subseteq [n{]}^2$, use three disjoint labelled vertex classes $X=[n]$, $Y=[n]$, $Z=[2n]$. Each $(x,y)\in A$ inserts the three edges $xy,x(x+y),y(x+y)$, producing pairwise edge-disjoint triangles. Every triangle in a graph with labels $(x,y,z)$ corresponds to the three points $(x,y),(x,z-x),(z-y,y)$ of $A$. It is canonical when $z=x+y$; otherwise it gives a corner in an integer grid with nonzero displacement $z-x-y$.

A graph automorphism is a bijection of the vertex set that preserves adjacency. It preserves graph distances and transports simple random-walk hitting problems between vertices.

A bridge is an edge whose deletion increases the number of components of a graph. Equivalently, it belongs to no cycle; within its original component, deleting it makes the connected graph disconnected.

The $d$-dimensional hypercube graph has vertex set $\{0,1{\}}^d$ and joins two vertices exactly when they differ in one coordinate. It is a $d$-regular bipartite graph on $2^d$ vertices.

A Gray code orders binary strings so that successive strings differ in exactly one bit. Consequently it describes a path in a hypercube graph; a cyclic Gray code describes a cycle.

The square lattice has vertex set ${\mathbb{Z}}^2$ and joins vertices whose Euclidean distance is one.

A graph is connected when every pair of vertices is joined by a path.

A connected component is a maximal connected subgraph.

For open-edge sets $S,T$ in a fixed finite graph, including isolated graph vertices in $k$, one has $k(S\cap T)+k(S\cup T)\ge k(S)+k(T)$. Incidence-vector spans have rank $r(S)=|V|-k(S)$; their union span is the sum of the two spans, while the intersection-edge span is contained in the intersection of spans. The vector-space dimension formula for a sum of subspaces proves submodularity of $r$, equivalently supermodularity of $k$.

A tree component is a graph component whose induced graph is a tree. A tree component with $j$ vertices has exactly $j-1$ edges.

The largest graph component is one with the most vertices. Ties may be broken arbitrarily; $L_1$ records the order, which is unaffected by the tie. For a sequence of random graphs, the size of its giant component is a central observable.

A vertex is one of the objects joined by the edges of a graph.

Two graphs are isomorphic when a bijection between their vertex sets preserves adjacency.

A triangle is a set of three vertices joined by all three possible edges, equivalently a copy of $K_3$.

A family of triangles in a graph is edge-disjoint if no edge belongs to two members. Any deletion of edges producing a triangle-free graph must remove at least one distinct edge for each member. The triangles in a graph may share vertices.

The triangle count of a finite simple graph is the number of unordered triples of vertices inducing a triangle in a graph. In a tripartite graph with parts $X,Y,Z$ and adjacency indicator functions $g_{XY},g_{YZ},g_{XZ}$, it equals $|X||Y||Z|{\mathbb{E}}_{x,y,z}{g}_{XY}(x,y)g_{YZ}(y,z)g_{XZ}(x,z)$, using uniform expectations on nonempty parts.

A triangle-free graph contains no triangle.

If every edge of a graph lies in at least one triangle, then the number of triangles is at least one third of the number of edges. Count edge-triangle incidences: each edge contributes at least one and each triangle contributes three.

The neighbourhood $\Gamma (v)$ of a vertex $v$ is the set of vertices adjacent to $v$.