Maintain lists of available colours, tentatively colour small random portions, erase conflicts and prune colours used by neighbours. In a triangle-free graph, a vertex's neighbours form an independent set, which enables local estimates. Track list size and average remaining neighbour congestion per colour; prune unusually congested colours before the next round. Concentration and the Lovász local lemma preserve these invariants until lists have enough slack for completion. Tracking averages matters because triangle-free graphs can still contain many four-cycles and need not have uniform per-colour congestion.

A proper vertex coloring assigns labels to the vertices of a graph so that vertices joined by an edge have different labels. Each colour class is an independent set. The chromatic number is the least number of labels needed for this form of graph coloring.

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

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

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.

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.

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

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.

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

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.

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.

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.

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.

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.

For the gradient superpotential Hamiltonian in supersymmetric quantum mechanics, $H_0={\sum }_a{A}_a^{†}{A}_a$. A zero-energy normalizable wavefunction therefore satisfies $A_{a}f=0$ for every $a$, because its energy is ${\sum }_a\Vert A_{a}f{\Vert }^2$. Equivalently ${\partial }_a(e^{-\chi }f)=0$, so on a connected configuration space $f=C{e}^{\chi }$. It exists in the Hilbert space precisely when $e^{\chi }$ is square-integrable. In three dimensions with radial $\chi$, this requires $4\pi {\int }_0^{\infty }{r}^2{e}^{2\chi (r)}dr<\infty$. The sign depends on the convention $A=\partial -\partial \chi$; the filled sector instead has the possible zero mode $e^{-\chi }$.

Gradient ascent seeks a maximum by stepping along the gradient of a differentiable objective. It is gradient descent applied to $-J$. Taylor expansion gives $J(x+\eta \nabla J)=J(x)+\eta \Vert \nabla J{\Vert }^2+O({\eta }^2)$, so sufficiently small positive steps improve the objective when the gradient is nonzero. Line search, projection onto admissible controls, and noise-aware gradient estimates are common practical modifications; a local stationary result need not be globally optimal.

For a point $P$ on a smooth projective genus-$g$ curve, Riemann-Roch space $L((g+1)P)$ has dimension at least two. A nonconstant function in it has only a pole at $P$, of order at most $g+1$, and extends to a finite morphism to the projective line. The degree equals the total pole order, including inseparable degree if present. This proves the bound.