Graph theory formulas

Holds for every undirected graph (loops count 2). So the number of odd-degree vertices is always even.

Attained exactly by the complete graph $K_n$. A $k$-regular simple graph on $n$ vertices has $m=nk/2$ edges, so it can exist only if $nk$ is even and $0\le k\le n-1$.

A graph with $n$ vertices and $k$ components has at least $n-k$ edges; so a connected graph has at least $n-1$ edges. Equality holds exactly for forests.

Simple graph on $n\ge 2$ vertices with at least 2 components. Attained by $K_{n-1}$ plus one isolated vertex. With exactly $k$ components the maximum is $\left(\genfrac{}{}{0ex}{}{n-k+1}{2}\right)$.

The vertex connectivity $\kappa (G)$ is the fewest vertices whose removal disconnects $G$ or leaves a single vertex; the edge connectivity $\lambda (G)$ is the fewest edges whose removal disconnects $G$. $\kappa (K_n)=\lambda (K_n)=n-1$. A connected graph on $n\ge 3$ vertices has a cut vertex exactly when $\kappa =1$, and a connected graph on $n\ge 2$ vertices has a bridge exactly when $\lambda =1$.

For a tree with $n\ge 2$ vertices. In particular every such tree has at least 2 leaves (vertices of degree 1).

Number of labelled trees on $n$ vertices, which equals the number of spanning trees of $K_n$. Also $\tau (K_{p,q})=p^{q-1}{q}^{p-1}$ and $\tau (C_n)=n$.

For a simple graph $G$, the complement $\overline{G}$ has the same vertices and exactly the non-edges of $G$. Degrees satisfy ${\mathrm{deg}}_{\overline{G}}(v)=n-1-{\mathrm{deg}}_G(v)$.

Necessary conditions on the order and size of a simple self-complementary graph. Examples: $P_4$ (4 vertices, 3 edges) and $C_5$ (5 vertices, 5 edges).

Holds for every simple (loopless) graph: a set is independent exactly when its complement is a vertex cover.

Every vertex cover needs a distinct vertex for each matching edge, so $\nu \le \beta$ always; equality is guaranteed only for bipartite graphs. (The triangle has $\nu =1$, $\beta =2$.)

A bipartite graph with parts $X,Y$ has a matching covering every vertex of $X$ if and only if this holds, where $N(S)$ is the set of neighbours of $S$. When $|X|=|Y|$, this is the condition for a perfect matching.

For every graph, where $\Delta$ is the maximum degree. By Brooks' theorem, a connected graph that is neither a complete graph nor an odd cycle has $\chi (G)\le \Delta (G)$.

$P(G,k)$ is the number of proper colourings of $G$ using at most $k$ colours, with the colours and vertices labelled. $T$ is any tree on $n$ vertices; $C_n$ needs $n\ge 3$. Check: $P(C_3,k)=k(k-1)(k-2)=P(K_3,k)$. $\chi (G)$ is the least $k$ with $P(G,k)>0$.

The chromatic index ${\chi }^{\prime }(G)$ is the fewest colours that give edges sharing a vertex different colours. The bounds hold for every simple graph (Vizing). A bipartite graph has ${\chi }^{\prime }=\Delta$. ${\chi }^{\prime }(K_n)=n-1$ for even $n$ and $n$ for odd $n$.

For a connected planar graph (drawn without crossings). With $k$ components the right side is $k+1$.

For a simple planar graph with $V\ge 3$. If the graph also has no triangle (for example, it is bipartite), $E\le 2V-4$. Reason: in a simple connected planar graph with $V\ge 3$, every face has degree at least 3 (at least 4 with no triangle), and ${\sum }_f\mathrm{deg}(f)=2E$. More generally, if every cycle has length at least $g$, then $E\le \frac{g}{g-2}(V-2)$.

Simple graph with $n\ge 3$. Ore's generalisation: if $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$ for every pair of non-adjacent $u,v$, then $G$ is Hamiltonian. Both are sufficient only.

For $n\ge 3$, labelled vertices, counting a cycle and its reverse as the same. $K_{p,q}$ is Hamiltonian exactly when $p=q\ge 2$, and $K_{n,n}$ ($n\ge 2$) has $\frac{n!(n-1)!}{2}$ Hamiltonian cycles (1 for $K_{2,2}$, 6 for $K_{3,3}$).

For the adjacency matrix $A$ of a graph (directed or undirected; in a multigraph $A_{ij}$ counts parallel edges, and a loop is entered as 1 in $A_{ii}$). Walks may repeat vertices.