##### Theorem5.9

Let \(\deg_\bfG(v)\) denote the degree of vertex \(v\) in graph \(\GVE\text{.}\) Then \begin{equation} \sum_{v\in V}\deg_\bfG(v) = 2|E|. \label{eq_graphs_degsum}\tag{5.1.1} \end{equation}

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.

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.

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.

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

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*}

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?

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.

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.

Let \(\deg_\bfG(v)\) denote the degree of vertex \(v\) in graph \(\GVE\text{.}\) Then \begin{equation} \sum_{v\in V}\deg_\bfG(v) = 2|E|. \label{eq_graphs_degsum}\tag{5.1.1} \end{equation}

For any graph, the number of vertices of odd degree is even.

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

Every tree on \(n\geq 2\) vertices has at least two leaves.