Graph ($G=(V,E)$)

A graph describes objects, called vertices, and pairwise connections, called edges. Its vertex set $V$ tells us what the objects are; $E$ records their connections. The basic abstraction retains graph adjacency while discarding positions, angles and Euclidean distances: moving the dots in a drawing changes none of the edges. A crossing of two drawn lines is not an extra vertex unless explicitly designated as one. Even the labels can change: a graph isomorphism is a relabelling that preserves graph adjacency in both directions.^[ref]

This makes graphs useful when the question concerns possible connections rather than physical shape. For example, model locations by vertices and direct links by edges; a graph path answers whether one location can reach another. Alternatively, let vertices be activities and edges represent conflicts: a graph coloring then assigns compatible time slots. These are mathematical models, so one must decide which pairwise relationship an edge means before applying graph theory.^[ref]

Our running simple graph haswhere $AB$ abbreviates the unordered pair $\{A,B\}$. It consists of two triangles in a graph, $ABC$ and $DEF$, joined by $CD$. The two drawings above have identical graph adjacency, even though their apparent lengths differ. What counts is that $C$ and $D$ are adjacent, whereas $A$ and $F$ are not.

Route questions require precise vocabulary. A walk is a sequence of consecutive adjacent vertices, permitting repetitions; its length counts traversed edges. A trail is a walk that repeats no edge; a graph path repeats no vertex. For a multigraph, the walk must also specify which parallel edge each step uses. For instance, $A,B,A,C,D,F$ is a length-five walk but not a trail, since it uses $AB$ twice. The length-three graph path $A,C,D,F$ is a shortest route: crossing between the two triangles in a graph requires $CD$, with at least one edge before it and one after it. Thus $d(A,F)=3$ in graph distance, regardless of the drawing.^[ref]

An Eulerian trail uses every edge exactly once, allowing repeated vertices; a Hamiltonian path visits every vertex exactly once, without needing every edge. Here $C,A,B,C,D,E,F,D$ is an Eulerian trail of length seven, whereas $A,B,C,D,E,F$ is a Hamiltonian path of length five. The first repeats $C,D$; the second omits $AC,DF$. Calling an Eulerian trail an "Eulerian path" must not be taken to impose our graph path convention.^[ref]

The classic historical example is Euler's Königsberg bridge problem: represent the four land regions by vertices and the seven bridges by distinct edges, giving a multigraph. Their degrees of vertices are $3,3,3,5$. In a trail using every edge, arrivals and departures pair at every internal vertex, so at most the two endpoints can have odd vertex degree. Four odd degrees of vertices therefore rule out such a route. This early foundational example of graph theory needs neither bridge lengths nor a geographical map. Euler's paper is conventionally associated with 1736, the volume's nominal year; the Euler Archive records its writing in 1735 and publication in 1741.^[ref][ref]

The set of edges of a specified graph. In a simple graph, an edge is determined by its endpoints; a multigraph additionally distinguishes parallel edges with the same endpoints. A subgraph can be specified by selecting a vertex set and an edge set whose endpoints belong to it.

In a finite graph, start with an active vertex set $A_0$ and thresholds $t_v$. An inactive vertex becomes active once sufficiently many neighbours are active, and activated vertices remain active. Add eligible vertices until no more can be added. If $C$ is any threshold-closed set containing $A_0$, induction shows every activated vertex lies in $C$. The terminal active set is itself closed, so it is the least such closure and is independent of the eligible-vertex processing order.

For integer thresholds, compute active-neighbour counts and keep a work queue of vertices newly reaching their thresholds. Each vertex is queued once and each edge is inspected a constant number of times, giving $O(|V|+|E|)$ running time. Strict-majority activation has $t_v=\lfloor \mathrm{deg}(v)/2\rfloor +1$, so an isolated inactive vertex never qualifies. A maximum priority queue of activation margins is an alternative implementation.

Allow individual vertices to switch in either direction according to a fixed neighbour threshold, while the objective is to maximize the number in one designated state. Let $C$ be the monotone threshold activation closure of the initially designated vertices. At every time in any legal switching sequence, the designated set remains a subset of $C$: a loss preserves inclusion, while a gain outside $C$ is impossible because all currently designated neighbours lie in $C$ and the outside vertex has too few neighbours there. This induction proves an upper bound of $|C|$ on every attainable designated population. The monotone sequence attains $C$ itself and is therefore globally optimal. Temporary losses cannot improve this objective.

The numerical label assigned to an edge $e$ of a graph. An edge weight can be negative when the model allows it. It is distinct from the vertex degree, which counts incident edges.

A spanning subgraph in which every vertex has vertex degree two. In a finite simple graph, its connected components of a graph are graph cycles. Removing a perfect matching from a cubic graph leaves a 2-factor.

A family of graphs is sparse when its edge count grows substantially more slowly than the square of its vertex count; a common convention is that $m=O(n)$, where $n$ and $m$ count vertices and edges. State the intended asymptotic convention explicitly. An adjacency list then uses fewer storage entries than an adjacency matrix.

Two vertices of a graph are adjacent if an edge joins them. A graph automorphism preserves this relation in both directions. In an intersection graph, adjacency can be defined by a prescribed dimension or cardinality of an intersection, so any ambient symmetry preserving that statistic acts by graph automorphisms.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

A self-loop is an edge whose two endpoints are the same vertex. In undirected total-degree counting it contributes two to the degree of a vertex, since both endpoints are incident to that vertex. Simple graphs exclude self-loops; the linearized chord diagram model retains them and starts from one self-loop.

For $N\ge 3$, the square torus graph has vertex set $(\mathbb{Z}/N\mathbb{Z}{)}^2$ and joins vertices differing by one in exactly one coordinate. It has $N^2$ vertices and $2N^2$ bonds. Translations act transitively on vertices; translations together with a quarter turn act transitively on bonds. A rectangle of side lengths at most $N-2$ has the same induced subgraph as its planar square lattice counterpart.

For a graph with a cellular embedding on a surface, the dual has one vertex for each face and an edge crossing each original edge between its adjacent faces. Each edge is counted, including a loop when the two incident faces coincide. The planar dual graph is the case of a planar embedding.

A graph whose every vertex has degree of a vertex three.

A finite simple graph that is a cubic graph and has a perfect matching admits a partition of a set of its edges into graph paths of length three.

Proof. Delete a perfect matching $M$. The remaining spanning subgraph has vertex degree two at every vertex, so it consists of disjoint graph cycles. Orient each cyclically, giving a successor bijection $s$. Replace each $uv\in M$ by the graph path $s(u),u,v,s(v)$. The four vertices are distinct: the successor edges are not in $M$, neither is a self-loop, and injectivity of $s$ excludes $s(u)=s(v)$. Every edge of $M$ appears once in the middle, and every other edge appears once at its unique tail. Thus the graph paths cover every edge exactly once. In particular, the perfect matching theorem for a cubic graph with at most two bridges guarantees this decomposition under its hypotheses.

Every finite connected cubic graph with at most two bridges has a perfect matching.

Proof. The handshaking lemma implies that the number $n$ of vertices is an even integer. Fix a nonempty subset $S$ of the vertex set, and let $q$ count the components of $G-S$ of odd integer order. For such a component $C$, counting vertex degrees gives $3|C|=2|E(C)|+d(C)$, where $d(C)$ counts its edges to $S$. Thus $d(C)$ is a positive odd integer. If it is one, the unique outgoing edge is a bridge; this happens for at most two components. For all others $d(C)\ge 3$. Therefore $3q-4\le 3|S|$. Meanwhile $q\equiv n-|S|\equiv |S|(\mathrm{mod}2)$. If $q>|S|$, the same parity would force $q\ge |S|+2$, contradicting the preceding bound. For $S=\varnothing$ there is one component of even integer order and hence $q=0$. Apply Tutte's theorem on perfect matchings.

The bipartite cubic graph with vertices $A_i,B_i$, $i\in \mathbb{Z}/7\mathbb{Z}$, and edges $A_i{B}_i,A_i{B}_{i+1},A_i{B}_{i-2}$. The three offsets give a Tait coloring.

Triangulate a torus using the seven vertices of the complete graph $K_7$ and oriented triangles $(i,i+1,i+3)$ and $(i,i+3,i+2)$, with indices modulo seven. Every edge occurs twice with opposite orientations; each vertex has a cyclic link. The Euler characteristic is $7-21+14=0$. Its dual graph is the Heawood graph. This dual map has seven disc faces, each adjacent to all the others, so it needs seven face colors although its edges have a Tait coloring.

Its vertices are pairs of vertices. Two distinct pairs are adjacent exactly when, in each coordinate, their entries are equal or adjacent in the corresponding graph. Cartesian products of independent sets are independent, giving supermultiplicativity of the independence number.

An iterated strong graph product has vertices that are words of length $m$ in the graph's vertex set. Distinct words are nonadjacent exactly when some coordinate contains distinct nonadjacent entries. This differs from the distance-based graph power.

The capacity is the exponential growth rate of the independence numbers of strong graph powers. Products of independent sets make these numbers supermultiplicative, and Fekete lemma gives the limit and its equality to the supremum. Passing to every second power gives $c(G⊠G)=c(G{)}^2$.

A fitting matrix over a field has nonzero diagonal entries and zero entries at distinct nonadjacent vertices. Its tensor powers fit strong graph powers. On an independent set the restricted matrix is diagonal and nonsingular, so its cardinality is at most the matrix rank. This yields the capacity upper bound over every field.

Choose points $a_v\in F^r$ and polynomials $f_v$ in a finite-dimensional polynomial space $M$, with $f_v(a_v)\ne 0$ and $f_v(a_w)=0$ for distinct nonadjacent vertices. Evaluation produces a fitting matrix of rank at most ${\dim }_{F}M$. Equivalently, tensoring the polynomial spaces gives linearly independent polynomials for every independent code in a strong power, proving $c(G)\le {\dim }_{F}M$.

In each word pattern with equally many $G$ and complement coordinates, pair the coordinates of the two types and put the same vertex label in each pair. Distinct labels are separated in one of the two graphs, making an independent code of size $n^m$ for a pattern of length $2m$. Distinct patterns lie in different graph components, so their codes combine to an independent set of size $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)n^m$. Taking $2m$th roots gives the displayed bound.

Capacity of a disjoint union can strictly exceed the sum of the capacities. On the five-element subsets of a twenty-point set, join distinct sets when their intersection is odd. Linear polynomials over ${\mathbb{F}}_2$ bound its capacity by twenty; squarefree quadratic polynomials over ${\mathbb{F}}_3$ bound its complement's capacity by $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. The complement-pair lower bound is $2\sqrt{\left(\genfrac{}{}{0ex}{}{20}{5}\right)}>210$, establishing strict nonadditivity.

These five words are independent in the strong square of the cycle graph $C_5$: a nonzero difference is a nonedge in the first or the second coordinate. A three-dimensional orthonormal representation with common vertical squared component $1/\sqrt{5}$ proves the matching upper bound. Consequently $c(C_5)=\vartheta (C_5)=\sqrt{5}$.

A vertex-edge incidence matrix records which vertices are endpoints of each edge of a graph. The unsigned convention uses entries one at the endpoints, with a convention for loops. Choosing an orientation gives the oriented incidence matrix, with minus one at the initial endpoint and plus one at the terminal endpoint. These are different conventions and should be specified when using the matrix in a computation.

A bounded-degree infinite graph is amenable when there are finite nonempty vertex sets $W_n$ such that $|{\partial }^{+}{W}_n|/|W_n|\to 0$, where ${\partial }^{+}{W}_n$ is the set of vertices outside $W_n$ adjacent to it. These are graph Følner sets. Amenability makes surface contributions negligible compared with volume. The square lattice and any periodic finite decoration of it are examples.

A finite nonempty vertex set in an amenable graph is a Følner set with tolerance $\epsilon$ if its external boundary has size at most $\epsilon$ times its volume. A graph Følner sequence consists of such sets with tolerances tending to zero. For a bounded-degree graph, every fixed-thickness boundary layer also has negligible relative volume along this sequence.

A multigraph permits distinct edges with the same pair of endpoints. Whether loops are also allowed is a convention that must be specified for a particular result. Counting edges with multiplicity differs from counting adjacent vertices.

A bouquet graph consists of one vertex and $j$ self-loops. Its vertex has degree $2j$, and its graph excess is $j-1$. The two-loop bouquet is one of the three possible kernels of a bicyclic graph; in a simple subdivision, each loop must expand to a cycle of length at least three.

An automorphism group is transitive on ordered pairs of vertices at every fixed distance. Grassmann graphs provide examples with the finite general linear group as a distance-transitive automorphism group.

A subgroup of the graph automorphism group acts distance-transitively when it is transitive on the ordered pairs of vertices at each fixed graph distance. Thus two vertex pairs at the same distance can be matched by one automorphism from that subgroup. Existence of such a subgroup implies that the full automorphism group has the same property, making the graph a distance-transitive graph. The specified subgroup need not be the entire automorphism group.

Vertices are Lagrangian subspaces of a $2m$-dimensional symplectic vector space, joined when they intersect in codimension one. A pair with intersection dimension $m-r$ admits a symplectic basis in which $U=⟨e_1,\dots ,e_m⟩$ and $W=⟨f_1,\dots ,f_r,e_{r+1},\dots ,e_m⟩$. Replacing $e_i$ successively by $f_i$ gives an isotropic path of length $r$, while one edge can increase intersection dimension with a fixed target by at most one. Equal-distance ordered pairs have the same adapted form, so the symplectic group acts distance-transitively.

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.

Maintain a frontier of partial states in a priority queue and expand the state with the best current priority. Correctness of a particular stopping rule depends on what the priority bounds. If every descendant has smaller priority than its ancestor, the frontier maximum also bounds the priority of every unseen descendant.

Best-first search prioritizing accumulated path cost, equivalently A-star search with zero heuristic function. With finite branching factor and positive lower-bounded step costs, tree search is complete for finite solutions and returns a least-cost goal if the goal test is applied on removal from the search frontier. Goal testing at generation can instead return an expensive edge before a cheaper multi-edge route is explored.

Best-first search using only a heuristic function estimating remaining goal cost, without adding accumulated path cost. A comparator supplying the same total ordering of estimates suffices to choose expansions even if numeric estimates are unavailable. In general it need not be a complete search algorithm or an optimal search algorithm; particular stronger information or finite-graph policies can supply additional guarantees.

In a finite reachable search problem with strictly positive step costs and a reachable goal, greedy best-first search using a perfect heuristic selects one parent–child chain until it reaches a goal state. At a selected nonterminal state $s$, an optimal first transition has $h^{\ast }(s^{\prime })=h^{\ast }(s)-c(s,s^{\prime })<h^{\ast }(s)$. Every older search frontier entry has estimate at least $h^{\ast }(s)$, so the next selected entry must be a newly generated child with smaller estimate. Repeating proves the chain property. In an infinite finitely branching problem, a positive uniform lower bound on costs also bounds the chain length by the initial remaining cost divided by that lower bound. Zero-cost ties can break the chain property; the lemma does not establish least accumulated path cost.

Best-first search prioritizing the estimated total solution cost $f=g+h$, with $g$ the cost already incurred and $h$ a heuristic function for the remaining cost. With nonnegative estimates, goal estimates zero, finite branching factor and step costs bounded below by a positive constant, the tree search version using an admissible heuristic returns a minimum-cost goal when it removes one for expansion. An optimal solution path always has a frontier node with $f\le C^{\ast }$; a more costly goal cannot be removed before it. The stated finiteness and lower-cost assumptions ensure finitely many earlier nodes when a finite solution exists. Repeated-state handling in graph search needs reopening when a better path is found, unless a consistent heuristic justifies finalizing expanded states.

Suppose $0\le h(n)\le h^{\ast }(n)\le u(n)$ in a search problem, with $h^{\ast }=\infty$ at dead ends. Every finite $g(n)+u(n)$ bounds some reachable solution cost from above, so their running minimum $B$ is at least the global optimum $C^{\ast }$. Every node of an optimal path has $g+h\le C^{\ast }\le B$, and therefore survives the displayed strict pruning rule. Ordinary A-star search can continue to a selected goal without receiving a path witnessing $u$.

Equality pruning is unsafe without a stored incumbent solution: when $B=C^{\ast }$, it could delete every optimal continuation. A numerical upper bound does not by itself provide a plan to return. This distinguishes an upper-bound certificate from a constructed solution in branch and bound.

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 graph is quasi-transitive if some group of graph automorphisms has finitely many vertex orbits. This is also called a graph of finite type. A connected graph that is infinite and a locally finite graph then has uniformly bounded degrees. Every orbit is infinite: a finite invariant orbit would have finite neighborhoods, and finitely many orbit types would put the entire graph in one such neighborhood. This permits finite sets to be moved arbitrarily far apart by graph automorphisms.

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.

The four-dimensional hypercube contains a graph subdivision of $K_{3,3}$, although no hypercube contains an ordinary $K_{3,3}$ subgraph: two distinct cube vertices have at most two common neighbors. One subdivision uses branch sets $\{0000,0011,1100\}$ and $\{0001,0010,0100\}$. Six connections are direct; the remaining paths are $0011\to 0111\to 0110\to 0100$, $1100\to 1101\to 0101\to 0001$, and $1100\to 1110\to 1010\to 0010$. Their internal vertices are distinct. Appending zero coordinates embeds the construction in every higher-dimensional cube, proving nonplanarity.

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.

Connectivity studies the existence of paths between vertices of a graph and the persistence of paths after vertex or edge deletions. A connected graph is the basic case in which every pair of vertices is linked by a path.

An undirected graph is connected when every pair $u,v$ of vertices is joined by a finite graph path. The length-zero graph path consisting of $u$ alone is allowed, so a single-vertex graph is connected. We use the term here for nonempty graphs; conventions for the graph with no vertices vary. Adjacent vertices are connected, but connected vertices need not be adjacent: in our six-vertex example, $A$ reaches $F$ along $A,C,D,F$, although $AF$ is absent.

Allowing walks instead of graph paths gives the same test for a connected graph. Whenever a finite walk revisits a vertex, delete the intervening closed portion; repeating this leaves a graph path with the same endpoints. This simple shortening argument explains why revisiting locations cannot help decide reachability.^[ref]

Connectivity can conceal fragile connections. Removing $CD$ from our graph produces two connected components of a graph, on $\{A,B,C\}$ and $\{D,E,F\}$: $CD$ is a bridge in a graph. Removing $AB$ instead preserves connectivity, because $A,C,B$ supplies an alternative graph path. If edges represent communication links, this calculation says precisely which single link failure separates the two groups. It is a conclusion about this model, independent of the lengths in its drawing.

A tree is a nonempty connected graph without a graph cycle; equivalently, each pair of vertices has exactly one graph path between them. Delete $BC$ and $EF$ from our example. The remaining edgesform a spanning tree: all six vertices remain, with $6-1=5$ edges. The graph path $A,C,D,F$ is now unique, and every remaining edge is a bridge in a graph. Adding $BC$ back creates exactly one graph cycle, $B,A,C,B$. Thus graph cycles express alternative routes, while a tree retains just enough connections for reachability. More generally, a finite connected graph on $n\ge 1$ vertices has at least $n-1$ edges, with equality exactly for a tree. One proof repeatedly removes an edge on a graph cycle, preserving connectivity, until a spanning tree remains.^[ref]

For a finite graph, breadth-first search tests connectivity by starting at one vertex and discovering neighbours in successive layers. Starting at $A$, the layers in our example are $\{A\}$, $\{B,C\}$, $\{D\}$, $\{E,F\}$. Every vertex is discovered, and the layer numbers give graph distances from $A$. Recording one discovery edge for each new vertex constructs a spanning tree. This turns an existence question into both a concrete route and a certificate of connectivity.

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.

Choose $n=d^7$ and a binomial random graph of edge probability $d/n$. With high probability its maximum degree is at most $2d$, it has $o(n)$ triangles, and every independent set has size at most $4n\log d/d$. Delete one vertex per triangle. The resulting triangle-free graph has chromatic number at least $d/(8\log d)$. Appending a disjoint star of degree $2d$, if necessary, makes the maximum degree exactly $2d$ without lowering the chromatic number. Thus the order $\Delta /\log \Delta$ is unavoidable.

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