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\mathrm{\ne }v\}\mathrm{.}$

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 $\mathrm{\mid }V\mathrm{\mid }$ and $\mathrm{\mid }E\mathrm{\mid }$ are those of The cardinality $\mid A\mid$ 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 $\mathrm{\mid }V\mathrm{\mid }$ and its size is $\mathrm{\mid }E\mathrm{\mid }$ (The cardinality $\mid A\mid$ of a finite set). The null graph has $V=\mathrm{\varnothing }$ and $E=\mathrm{\varnothing }$. An edgeless graph has $E=\mathrm{\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\mathrm{\ne }\mathrm{\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\},N_G[v]:=N_G(v)\cup \{v\}\mathrm{.}$

The degree of $v$ is ${\mathrm{deg}}_G(v):=\mathrm{\mid }{N}_G(v)\mathrm{\mid }$, 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\mathrm{\ne }\mathrm{\varnothing }$, the minimum degree and maximum degree are

$\delta (G):={\min }_{v\in V}{\mathrm{deg}}_G(v),\mathrm{\Delta }(G):={\max }_{v\in V}{\mathrm{deg}}_G(v)\mathrm{.}$

They are defined because $V$ is a nonempty finite set (The cardinality $\mid A\mid$ of a finite set). Neither $\delta (G)$ nor $\mathrm{\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)\mathrm{.}$

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 $\mathrm{\ell }$ is a finite vertex list

$W=(v_0,v_1,\dots ,v_{\mathrm{\ell }})$

such that $\{v_{i-1},v_i\}\in E$ for every $1\le i\le \mathrm{\ell }$. Its endpoints are $v_0$ and $v_{\mathrm{\ell }}$. The length is the number $\mathrm{\ell }$ of traversed edges, not the number of displayed vertices. A walk is closed when $v_0=v_{\mathrm{\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,\dots ,v_{\mathrm{\ell }-1},v_{\mathrm{\ell }}=v_0)$ of length $\mathrm{\ell }\ge 3$ in which $v_0,\dots ,v_{\mathrm{\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,\dots ,v_{\mathrm{\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_{\mathrm{\ell }}$ of length at most $\mathrm{\ell }$. If $W$ repeats a vertex, the resulting path can be chosen to have length strictly less than $\mathrm{\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\}\mathrm{.}$

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\mathrm{/}\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 \{\mathrm{\ell }\in \mathbb{N}:\text{some path from }u\text{ to }v\text{ has length }\mathrm{\ell }\}\mathrm{.}$

The set being minimized is nonempty by connectivity and finite because a path has no repeated vertex and $V(G)$ is finite (The cardinality $\mid A\mid$ 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)=\mathrm{\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)\ge 0$, 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)\mathrm{\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 $\mathrm{\varnothing }$ and the complete graph $K_V$ has edge set $[V{]}^2$. When $V$ is an $n$-element labelled set, these are also denoted ${\bar{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\}\mathrm{.}$

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

The path graph $P_n$ has $n$ vertices. For $n\ge 1$, take vertices $0,\dots ,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\ge 3$: it has vertices $0,\dots ,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 $\mathrm{\Omega }$. The Petersen graph has vertex set $[\mathrm{\Omega }{]}^2$, the set of two-element subsets of $\mathrm{\Omega }$, and edge set

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

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 $\left(\genfrac{}{}{0px}{}{5}{2}\right)=10$ elements by A finite set with $n$ elements has exactly $\left(\genfrac{}{}{0px}{}{n}{2}\right)$ two-element subsets, and $2\left(\genfrac{}{}{0px}{}{n}{2}\right)=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 $\phi :V\to W$ (Injection, surjection, bijection) such that, for all distinct $u,v\in V$,

$\{u,v\}\in E⟺\{\phi (u),\phi (v)\}\in F\mathrm{.}$

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

$\bar{G}:=(V,[V{]}^2\setminus E)\mathrm{.}$

Thus exactly one of $G$ and $\bar{G}$ contains any given pair of distinct vertices as an edge, and $\overline{\stackrel{‾}{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^{\mathrm{\prime }}=(V\setminus \{u,v\})\cup \{x_e\}$, and let $q:V\to V^{\mathrm{\prime }}$ send $u,v$ to $x_e$ and fix every other vertex. Then

$G\mathrm{/}e:=(V^{\mathrm{\prime }},\{q[f]:f\in E\setminus \{e\},\mathrm{\mid }q[f]\mathrm{\mid }=2\})\mathrm{.}$

The condition $\mathrm{\mid }q[f]\mathrm{\mid }=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\mathrm{\ne }\mathrm{\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}{\mathrm{deg}}_G(v)=2\mathrm{\mid }E\mathrm{\mid }$

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 $\left(\genfrac{}{}{0px}{}{n}{2}\right)$ edges.

On a fixed labelled $n$-element vertex set $V$, there are exactly $2^{\left(\genfrac{}{}{0px}{}{n}{2}\right)}$ finite simple graphs.

Let $G=(V,E)$ be connected with $n=\mathrm{\mid }V\mathrm{\mid }\ge 2$. 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 \{\mathrm{\mid }S\mathrm{\mid }:S\text{ is a vertex cut}\},\lambda (G):=\min \{\mathrm{\mid }F\mathrm{\mid }:F\text{ is an edge cut}\}\mathrm{.}$

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.

Let $G$ be a finite graph and let $e$ be an edge. Using edge deletion from Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors and connected components from Connected graphs and connected components defined by the existence of vertex paths, the edge $e$ is a bridge if $G-e$ has more connected components than $G$. Component vertex sets partition the graph as in The connected components of a graph partition its vertex set and are its maximal connected subgraphs, so this comparison is unambiguous even when $G$ is disconnected.

For every edge $e$ of a finite graph $G$, $e$ is a bridge (A bridge as an edge whose deletion increases the number of connected components) if and only if $e$ lies on no cycle (Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges). Connectivity and deletion have the meanings of Connected graphs and connected components defined by the existence of vertex paths and Vertex and edge deletion, edge contraction, graph minors, subdivisions and topological minors.

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)\mathrm{.}$

This includes complete graphs under the convention $\kappa (K_n)=n-1$: for $K_n$ with $n\ge 2$, all three quantities equal $n-1$.

Every nonempty finite simple graph $G$ contains a path having at least $\delta (G)$ edges.