Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section5.1Basic Notation and Terminology for Graphs

A graph \(\bfG\) is a pair \((V,E)\) where \(V\) is a set (almost always finite) and \(E\) is a set of \(2\)-element subsets of \(V\text{.}\) Elements of \(V\) are called vertices and elements of \(E\) are called edges. We call \(V\) the vertex set of \(\bfG\) and \(E\) is the edge set. For convenience, it is customary to abbreviate the edge \(\{x,y\}\) as just \(xy\text{.}\) Remember though that \(xy\in E\) means exactly the same as \(yx\in E\text{.}\) If \(x\) and \(y\) are distinct vertices from \(V\text{,}\) \(x\) and \(y\) are adjacent when \(xy\in E\text{;}\) otherwise, we say they are non-adjacent. We say the edge \(xy\) is incident to the vertices \(x\) and \(y\text{.}\)

For example, we could define a graph \(\GVE\) with vertex set \(V=\{a,b,c,d,e\}\) and edge set \(E=\{\{a,b\},\{c,d\},\{a,d\}\}\text{.}\) Notice that no edge is incident to \(e\text{,}\) which is perfectly permissible based on our definition. It is quite common to identify a graph with a visualization in which we draw a point for each vertex and a line connecting two vertices if they are adjacent. The graph \(\bfG\) we've just defined is shown in Figure 5.1. It's important to remember that while a drawing of a graph is a helpful tool, it is not the same as the graph. We could draw \(\bfG\) in any of several different ways without changing what it is as a graph.

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.1A graph on \(5\) vertices

As is often the case in science and mathematics, different authors use slightly different notation and terminology for graphs. As an example, some use nodes and arcs rather than vertices and edges. Others refer to vertices as points and in this case, they often refer to lines rather than edges. We will try to stick to vertices and edges but confess that we may occasionally lapse into referring to vertices as points. Also, following the patterns of many others, we will also say that adjacent vertices are neighbors. And we will use the more or less standard terminology that the neighborhood of a vertex \(x\) is the set of vertices adjacent to \(x\text{.}\) Thus, using the graph \(\bfG\) we have depicted in Figure 5.1, vertices \(d\) and \(a\) are neighbors, and the neighborhood of \(d\) is \(\{a,c\}\) while the neighborhood of \(e\) is the empty set. Also, the degree of a vertex \(v\) in a graph \(\bfG\text{,}\) denoted \(\deg_\bfG(v)\text{,}\) is then the number of vertices in its neighborhood, or equivalently, the number of edges incident to it. For example, we have \(\deg_\bfG(d)=\deg_\bfG(a)=2\text{,}\) \(\deg_\bfG(c)=\deg_\bfG(b)=1\text{,}\) and \(\deg_\bfG(e)=0\text{.}\) If the graph being discussed is clear from context, it is not uncommon to omit the subscript and simply write \(\deg(v)\) for the degree of \(v\text{.}\)

When \(\GVE\) and \(\HWF\) are graphs, we say \(\bfH\) is a subgraph of \(\bfG\) when \(W\subseteq V\) and \(F\subseteq E\text{.}\) We say \(\bfH\) is an induced subgraph when \(W\subseteq V\) and \(F=\{xy\in E: x,y\in W\}\text{.}\) In other words, an induced subgraph is defined completely by its vertex set and the original graph \(\bfG\text{.}\) We say \(\bfH\) is a spanning subgraph when \(W=V\text{.}\) In Figure 5.2, we show a graph, a subgraph and an induced subgraph. Neither of these subgraphs is a spanning subgraph.

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.2A Graph, a Subgraph and an Induced Subgraph

A graph \(\GVE\) is called a complete graph when \(xy\) is an edge in \(\bfG\) for every distinct pair \(x,y\in V\text{.}\) Conversely, \(\bfG\) is an independent graph if \(xy\not\in E\text{,}\) for every distinct pair \(x,y\in V\text{.}\) It is customary to denote a complete graph on \(n\) vertices by \(\bfK_n\) and an independent graph on \(n\) vertices by \(\bfI_n\). In Figure 5.3, we show the complete graphs with at most \(5\) vertices.

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.3Small complete graphs

A sequence \((x_1,x_2,\dots,x_n)\) of vertices in a graph \(\GVE\) is called a walk when \(x_ix_{i+1}\) is an edge for each \(i=1,2,\dots,n-1\text{.}\) Note that the vertices in a walk need not be distinct. On the other hand, if the vertices are distinct, then the sequence is called a path, and often to emphasize where a path starts and ends, we will say that a sequence \((x_1,x_2,\dots,x_n)\) of distinct vertices is a path from \(x_1\) to \(x_n\) in \(\bfG\text{.}\) Similarly, when \(n\ge3\text{,}\) a path \((x_1,x_2,\dots,x_n)\) of \(n\) distinct vertices is called a cycle when \(x_1x_n\) is also an edge in \(\bfG\text{.}\) It is customary to denote a path on \(n\) vertices by \(\bfP_n\), while \(\bfC_n\) denotes a cycle on \(n\) vertices. The length of a path or a cycle is the number of edges it contains. Therefore, the length of \(\bfP_n\) is \(n-1\) and the length of \(\bfC_n\) is \(n\text{.}\) In Figure 5.4, we show the paths of length at most \(4\text{,}\) and in Figure 5.5, we show the cycles of length at most \(5\text{.}\)

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.4Short paths

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.5Small cycles

If \(\GVE\) and \(\HWF\) are graphs, we say \(\bfG\) is isomorphic to \(\bfH\) and write \(\bfG\cong\bfH\) when there exists a bijection \(f:V\bijection W\) so that \(x\) is adjacent to \(y\) in \(\bfG\) if and only if \(f(x)\) is adjacent to \(f(y)\) in \(\bfH\text{.}\) Often writers will say that \(\bfG\) “contains” \(\bfH\) when there is a subgraph of \(\bfG\) which is isomorphic to \(\bfH\text{.}\) In particular, it is customary to say that \(\bfG\) contains the cycle \(\bfC_n\) (same for \(\bfP_n\) and \(\bfK_n\)) when \(\bfG\) contains a subgraph isomorphic to \(\bfC_n\text{.}\) The graphs in Figure 5.6 are isomorphic. An isomorphism between these graphs is given by

\begin{equation*} f(a)=5,\quad f(b) = 3, \quad f(c) = 1,\quad f(d) = 6,\quad f(e)=2,\quad f(h)=4. \end{equation*}

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.6A pair of isomorphic graphs

On the other hand, the graphs shown in Figure 5.7 are not isomorphic, even though they have the same number of vertices and the same number of edges. Can you tell why?

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.7A pair of nonisomorphic graphs

A graph \(\bfG\) is connected when there is a path from \(x\) to \(y\) in \(\bfG\text{,}\) for every \(x,y\in V\text{;}\) otherwise, we say \(\bfG\) is disconnected. The graph of Figure 5.1 is disconnected (a sufficient justification for this is that there is no path from \(e\) to \(c\)), while those in Figure 5.6 are connected. If \(\bfG\) is disconnected, we call a maximal connected subgraph of \(\bfG\) a component. By this we mean that a subgraph \(\bfH\) of \(\bfG\) is a component of \(\bfG\) provided that there does not exist a connected subgraph \(\bfH'\) of \(\bfG\) such that \(\bfH\) is a subgraph of \(\bfH'\text{.}\)

A graph is acyclic when it does not contain any cycle on three or more vertices. Acyclic graphs are also called forests. A connected acyclic graph is called a tree. When \(\GVE\) is a connected graph, a subgraph \(\HWF\) of \(\bfG\) is called a spanning tree if \(\bfH\) is both a spanning subgraph of \(\bfG\) and a tree. In Figure 5.8, we show a graph and one of its spanning trees. We will return to the subject of spanning trees in Chapter 12.

<<SVG image is unavailable, or your browser cannot render it>>

Figure5.8A Graph and a Spanning Tree

The following theorem is very elementary, and some authors refer to it as the “first theorem of graph theory”. However, this basic result can be surprisingly useful.

Proof

We will return to the topic of trees later, but before moving on, let us prove one elementary proposition about trees. First, a leaf in a tree \(\bfT\) is a vertex \(v\) with \(\deg_\bfT(v)=1\text{.}\)