Graphs, Walks and Connectivity

A finite simple graph is an ordered pair $G=(V,E)$ in which $V$ is a finite set and

$E\subseteq [V]^2:=\{\,\{u,v\}\subseteq V: u\ne v\,\}.$

The elements of $V=V(G)$ are the vertices and the elements of $E=E(G)$ are the edges. Thus every edge has two distinct endpoints, there are no loops, and an unordered pair of vertices occurs as at most one edge. Finiteness and the notation $|V|$ and $|E|$ are those of The cardinality $\lvert A\rvert$ of a finite set.

When no qualifier is present, the word graph has this meaning.

For a graph $G=(V,E)$ (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets), its order is $|V|$ and its size is $|E|$ (The cardinality $\lvert A\rvert$ of a finite set). The null graph has $V=\varnothing$ and $E=\varnothing$. An edgeless graph has $E=\varnothing$ but may have vertices. Thus the null graph is the unique graph with no vertices, while an edgeless graph need not be null.

All sums indexed by $V$ or $E$ use their ordinary empty values. A minimum or maximum taken over the vertex set is used only when $V\ne\varnothing$; in particular, minimum and maximum degree are not assigned values for the null graph. Connectivity conventions for the null graph and the one-vertex graph are stated with the definition of connectivity.

A finite undirected multigraph consists of a finite vertex set $V$, a finite edge set $M$, and an endpoint map assigning to each $e\in M$ either a singleton $\{v\}$ or a two-element subset $\{u,v\}$ of $V$. An edge assigned $\{v\}$ is a loop at $v$. Distinct members of $M$ assigned the same endpoint set are parallel edges.

A finite directed graph, or digraph, consists of a finite vertex set $V$ and a set $A\subseteq V\times V$ of arcs. An arc $(u,v)$ is directed from $u$ to $v$; an arc $(v,v)$ is a directed loop.

These objects are variants, not instances of the default graph convention in A finite simple graph is a finite vertex set together with a set of two-element vertex subsets and Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here. A theorem stated merely for a graph therefore neither permits loops or parallel edges nor supplies directions to its edges.

Let $G=(V,E)$ be a graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

Distinct vertices $u,v$ are adjacent, or neighbours, when $\{u,v\}\in E$. A vertex $v$ and an edge $e$ are incident when $v\in e$. The open neighbourhood and closed neighbourhood of $v$ are

$N_G(v):=\{\,u\in V:\{u,v\}\in E\,\},\qquad N_G[v]:=N_G(v)\cup\{v\}.$

The degree of $v$ is $\deg_G(v):=|N_G(v)|$, equivalently the number of edges incident with $v$. A graph is $r$-regular when every vertex has degree $r$; it is cubic when it is $3$-regular. The multiset of the vertex degrees, usually written in nonincreasing order, is the degree sequence.

When $V\ne\varnothing$, the minimum degree and maximum degree are

$\delta(G):=\min_{v\in V}\deg_G(v),\qquad \Delta(G):=\max_{v\in V}\deg_G(v).$

They are defined because $V$ is a nonempty finite set (The cardinality $\lvert A\rvert$ of a finite set). Neither $\delta(G)$ nor $\Delta(G)$ is defined for the null graph.

Let $G=(V,E)$ be a graph. A graph $H=(W,F)$ is a subgraph of $G$ when $W\subseteq V$ and $F\subseteq E\cap[W]^2$.

For $W\subseteq V$, the subgraph induced by $W$ is

$G[W]:=(W,\ E\cap[W]^2).$

Thus it retains every edge of $G$ whose two endpoints lie in $W$. A subgraph $H=(W,F)$ is induced when $H=G[W]$, and it is spanning when $W=V$. These constructions remain finite simple graphs by A finite simple graph is a finite vertex set together with a set of two-element vertex subsets.

Let $G=(V,E)$ be a graph. A walk of length $\ell$ is a finite vertex list

$W=(v_0,v_1,\ldots,v_\ell)$

such that $\{v_{i-1},v_i\}\in E$ for every $1\le i\le\ell$. Its endpoints are $v_0$ and $v_\ell$. The length is the number $\ell$ of traversed edges, not the number of displayed vertices. A walk is closed when $v_0=v_\ell$.

A trail is a walk in which the traversed edges are distinct. A path is a walk in which the vertices are distinct. In particular, $(v)$ is a path of length $0$ from $v$ to itself.

A cycle is a closed walk $(v_0,\ldots,v_{\ell-1},v_\ell=v_0)$ of length $\ell\ge3$ in which $v_0,\ldots,v_{\ell-1}$ are distinct. A graph is acyclic when it contains no cycle. Reversing any walk, trail, path, or cycle preserves its type and length.

Let $W=(v_0,\ldots,v_\ell)$ be a walk in a graph. By deleting zero or more closed segments from its vertex list, one obtains a path from $v_0$ to $v_\ell$ of length at most $\ell$. If $W$ repeats a vertex, the resulting path can be chosen to have length strictly less than $\ell$.

Vertices $u$ and $v$ of a graph $G$ are connected, or reachable from one another, when a path in $G$ has endpoints $u$ and $v$. Equivalently, a walk joins them, because Every walk between two vertices contains a path between the same endpoints turns such a walk into a path.

For $v\in V(G)$, its connected component is the induced subgraph on

$C_G(v):=\{\,u\in V(G):u\text{ is reachable from }v\,\}.$

A graph is connected when its vertex set is nonempty and every two vertices are reachable from one another. Thus the null graph is not connected. The one-vertex graph is connected, since its vertex is joined to itself by the path of length $0$ from Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges.

On the vertex set of a graph, define $u\sim v$ when a walk joins $u$ to $v$. Then $\sim$ is an equivalence relation (Equivalence relation, equivalence class, and the quotient set $A/{\sim}$), and $u\sim v$ holds exactly when a path joins $u$ to $v$.

The vertex sets $C_G(v)$ of the connected components of a graph $G$ are nonempty, cover $V(G)$, and any two are equal or disjoint. Each induced graph $G[C_G(v)]$ is connected and contains every connected subgraph of $G$ that contains $v$. Consequently the connected components are precisely the maximal connected subgraphs of $G$.

Let $u$ and $v$ lie in the same connected component of a graph $G$. Their distance is

$d_G(u,v):=\min\{\,\ell\in\mathbb N:\text{some path from }u\text{ to }v\text{ has length }\ell\,\}.$

The set being minimized is nonempty by connectivity and finite because a path has no repeated vertex and $V(G)$ is finite (The cardinality $\lvert A\rvert$ of a finite set). No ordinary natural-number distance is assigned to vertices in different components.

For a vertex $v$, its eccentricity is the maximum of $d_G(v,u)$ over the vertices $u$ in its component. The diameter of a connected graph is the maximum of $d_G(u,v)$ over all pairs of its vertices. Thus every component has its own diameter, while a disconnected graph has no single graph diameter under this convention.

The girth $g(G)$ is the minimum length of a cycle in $G$. If $G$ is acyclic, set $g(G)=\infty$ by convention. This symbol records absence of a cycle and is not a distance between vertices.

Let $C$ be the vertex set of a connected component of a graph $G$. The function $d_G:C\times C\to\mathbb N$ satisfies, for all $u,v,w\in C$,

1. $d_G(u,v)\ge0$, with $d_G(u,v)=0$ if and only if $u=v$;
2. $d_G(u,v)=d_G(v,u)$;
3. $d_G(u,w)\le d_G(u,v)+d_G(v,w)$.

These are the metric axioms, so shortest-path distance is a metric on $C$.

A graph $G=(V,E)$ is bipartite when there are disjoint subsets $A,B\subseteq V$ with $V=A\cup B$ such that every edge has one endpoint in $A$ and the other in $B$. The ordered pair $(A,B)$ is a bipartition.

Equivalently, a proper two-colouring is a map $c:V\to\{0,1\}$ satisfying $c(u)\ne c(v)$ whenever $\{u,v\}\in E$: take $A=c^{-1}[\{0\}]$ and $B=c^{-1}[\{1\}]$, or define $c$ from a bipartition. Either part may be empty, so every edgeless graph, including the null graph, is bipartite.

Every closed walk of odd length in a graph contains, among its traversed edges, a cycle of odd length.

A finite simple graph is bipartite if and only if it contains no cycle of odd length.

On a finite vertex set $V$, the empty graph has edge set $\varnothing$ and the complete graph $K_V$ has edge set $[V]^2$. When $V$ is an $n$-element labelled set, these are also denoted $\overline K_n$ and $K_n$.

For disjoint finite sets $A$ and $B$, the complete bipartite graph $K_{A,B}$ has vertex set $A\cup B$ and edge set

$\{\,\{a,b\}:a\in A,\ b\in B\,\}.$

If $|A|=m$ and $|B|=n$, it is denoted $K_{m,n}$.

The path graph $P_n$ has $n$ vertices. For $n\ge1$, take vertices $0,\ldots,n-1$ and edges $\{i,i+1\}$ for $0\le i<n-1$; it has length $n-1$. Set $P_0$ equal to the null graph. The cycle graph $C_n$ is defined only for $n\ge3$: it has vertices $0,\ldots,n-1$, the consecutive edges $\{i,i+1\}$ for $0\le i<n-1$, and the closing edge $\{n-1,0\}$. Thus in this notation the subscript records the number of vertices, not the length of a path.

Fix a five-element set $\Omega$. The Petersen graph has vertex set $[\Omega]^2$, the set of two-element subsets of $\Omega$, and edge set

$\{\,\{A,B\}\subseteq [\Omega]^2:|\{A,B\}|=2\text{ and }A\cap B=\varnothing\,\}.$

In words, two vertices are adjacent exactly when the corresponding two-element subsets are disjoint. This is a finite simple graph, and its vertex set has $\binom52=10$ elements by A finite set with $n$ elements has exactly $\binom{n}{2}$ two-element subsets, and $2\binom{n}{2} = n(n-1)$. The definition is independent of the names assigned to the five elements, because a relabelling preserves disjointness.

Let $G=(V,E)$ and $H=(W,F)$ be graphs. A graph isomorphism is a bijection $\varphi:V\to W$ (Injection, surjection, bijection) such that, for all distinct $u,v\in V$,

$\{u,v\}\in E\quad\Longleftrightarrow\quad\{\varphi(u),\varphi(v)\}\in F.$

Graphs are isomorphic, written $G\cong H$, when such a map exists. An automorphism of $G$ is an isomorphism from $G$ to itself.

The complement of $G$ is the graph

$\overline G:=(V,[V]^2\setminus E).$

Thus exactly one of $G$ and $\overline G$ contains any given pair of distinct vertices as an edge, and $\overline{\overline G}=G$.

Let $G=(V,E)$ be a graph. For $v\in V$, vertex deletion gives $G-v:=G[V\setminus\{v\}]$. For $e\in E$, edge deletion gives $G-e:=(V,E\setminus\{e\})$. The same notation is used for deleting a set of vertices or edges.

For an edge $e=\{u,v\}$, contracting $e$ identifies $u$ and $v$. More precisely, take a new vertex $x_e$, put $V'=(V\setminus\{u,v\})\cup\{x_e\}$, and let $q:V\to V'$ send $u,v$ to $x_e$ and fix every other vertex. Then

$G/e:=\bigl(V',\ \{\,q[f]:f\in E\setminus\{e\},\ |q[f]|=2\,\}\bigr).$

The condition $|q[f]|=2$ deletes loops, while writing the edge family as a set merges parallel edges. Thus contraction returns a simple graph.

A graph $H$ is a minor of $G$ when it can be obtained by vertex deletions, edge deletions and edge contractions. Subdividing an edge $\{u,v\}$ replaces it by $\{u,x\}$ and $\{x,v\}$ for a new vertex $x$. A subdivision repeats this operation zero or more times. The graph $H$ is a topological minor of $G$ when some subdivision of $H$ is isomorphic to a subgraph of $G$ (Subgraphs, induced subgraphs and spanning subgraphs).

For a graph $G=(V,E)$, its line graph $L(G)$ has vertex set $E$. Distinct vertices $e,f\in E$ are adjacent in $L(G)$ exactly when the edges $e$ and $f$ of $G$ share an endpoint, that is, when $e\cap f\ne\varnothing$.

Because $E$ is finite and adjacency is recorded as a set of two-element subsets of $E$, the line graph is again a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets). Incidence in $G$ has become adjacency in $L(G)$.

For every finite simple graph $G=(V,E)$,

$\sum_{v\in V}\deg_G(v)=2|E|$

as an identity of natural numbers. It remains valid for the null graph, when both sides are $0$.

In every finite simple graph, the set of vertices having odd degree has even cardinality.

If $V$ is an $n$-element set, then the complete graph $K_V$ has exactly $\binom n2$ edges.

On a fixed labelled $n$-element vertex set $V$, there are exactly $2^{\binom n2}$ finite simple graphs.

Let $G=(V,E)$ be connected with $n=|V|\ge2$. A vertex cut is a set $S\subseteq V$ for which $G-S$ is disconnected or has at most one vertex. An edge cut is a set $F\subseteq E$ for which $G-F$ is disconnected. The vertex connectivity and edge connectivity are

$\kappa(G):=\min\{\,|S|:S\text{ is a vertex cut}\,\},\qquad\lambda(G):=\min\{\,|F|:F\text{ is an edge cut}\,\}.$

The finite families being minimized are nonempty: deleting all but one vertex is a vertex cut, and deleting all edges is an edge cut. For the complete graph $K_n$, no deletion leaving at least two vertices disconnects it, so the first definition gives the standard exceptional convention $\kappa(K_n)=n-1$.

For the one-vertex graph $K_1$, set $\kappa(K_1)=\lambda(K_1)=0$. The null graph and every disconnected graph are outside the domain of these two connectivity parameters under this convention. Thus the inequalities involving $\delta(G)$ are stated only for nontrivial connected graphs, where the vertex set is nonempty and $\delta(G)$ is defined.

For every connected finite simple graph $G$ with at least two vertices, $\lambda(G)\le\delta(G)$.

For every connected finite simple graph $G$ with at least two vertices, $\kappa(G)\le\lambda(G)$.

For every connected finite simple graph $G$ with at least two vertices,

$\kappa(G)\le\lambda(G)\le\delta(G).$