5.1: Basic Notation and Terminology for Graphs

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

For example, we could define a graph \(G=(V,E)\) with vertex set \(V=\{a,b,c,d,e\}\) and edge set \(E=\{\{a,b\},\{c,d\},\{a,d\}\}\). Notice that no edge is incident to ,e, 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 \(G\) 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 \(G\) in any of several different ways without changing what it is as a graph.

Figure 5.1. A 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\). Thus, using the graph \(G\) 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 \(G\), denoted \(deg_G⁡(v)\), is then the number of vertices in its neighborhood, or equivalently, the number of edges incident to it. For example, we have \(deg_G⁡(d)=deg_G⁡(a)=2, ,deg_G⁡(c)=deg_G⁡(b)=1\), and \(deg_G⁡(e)=0\). 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\).

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

Figure 5.2. A Graph, a Subgraph and an Induced Subgraph

A graph G \(=(V,E)\) is called a complete graph when \(xy\) is an edge in G for every distinct pair \(x,y \in V\). Conversely, G is an independent graph if \(xy \in E\), for every distinct pair \(x,y \in V\). It is customary to denote a complete graph on \(n\) vertices by \(K_n\) and an independent graph on \(n\) vertices by \(I_n\). In Figure 5.3, we show the complete graphs with at most 5 vertices.

Figure 5.3. Small complete graphs

A sequence \((x_1,x_2,…,x_n)\) of vertices in a graph G=\((V,E)\) is called a walk when \(x_ix_{i+1}\) is an edge for each \(i=1,2,…,n−1\). 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,…,x_n)\) of distinct vertices is a path from \(x_1\) to \(x_n\) in G. Similarly, when \(n \geq 3\), a path \((x_1,x_2,…,x_n)\) of \(n\) distinct vertices is called a cycle when \(x_1x_n\) is also an edge in G. It is customary to denote a path on n vertices by \(P_n\), while \(C_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 \(P_n\) is \(n−1\) and the length of \(C_n\) is \(n\). In Figure 5.4, we show the paths of length at most 4, and in Figure 5.5, we show the cycles of length at most 5.

Figure 5.4. Short paths

Figure 5.5. Small cycles

If \(G = (V,E)\) and \(H = (W,F)\) are graphs, we say \(G\) is isomorphic to \(H\) and write \(G≅H\) when there exists a bijection \(f: V \xrightarrow[onto]{1-1} W\) so that \(x\) is adjacent to \(y\) in \(G\) if and only if \(f(x)\) is adjacent to \(f(y)\) in \(H\). Often writers will say that \(G\) “contains” \(H\) when there is a subgraph of \(G\) which is isomorphic to \(H\). In particular, it is customary to say that \(G\) contains the cycle \(C_n\) (same for \(P_n\) and \(K_n\)) when \(G\) contains a subgraph isomorphic to \(C_n\). The graphs in Figure 5.6 are isomorphic. An isomorphism between these graphs is given by

\(f(a) = 5, f(b) = 3, f(c)=1, f(d)=6, f(e)=2, f(h)=4\).

Figure 5.6. A 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?

Figure 5.7. A pair of nonisomorphic graphs

A graph \(G\) is connected when there is a path from \(x\) to \(y\) in \(G\), for every \(x,y \in V\); otherwise, we say \(G\) 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 \(G\) is disconnected, we call a maximal connected subgraph of \(G\) a component. By this we mean that a subgraph \(H\) of \(G\) is a component of \(G\) provided that there does not exist a connected subgraph \(H′\) of \(G\) such that \(H\) is a subgraph of \(H'\).

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 \(G=(V,E)\) is a connected graph, a subgraph \(H=(W,F)\) of \(G\) is called a spanning tree if \(H\) is both a spanning subgraph of \(G\) 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.

Figure 5.8. A 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.

Theorem 5.9.

Let \(degG⁡(v)\) denote the degree of vertex \(v\) in graph \(G=(V,E)\). Then

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

Proof

We consider how many times an edge \(e=vw \in E\) contributes to each side of (5.1.1). The \(deg_G⁡(x)\) and \(deg_G⁡(y)\) terms on the left hand side each count \(e\) once, so \(e\) is counted twice on that side. On the right hand side, \(e\) is clearly counted twice. Therefore, we have the equality claimed.

Corollary 5.10.

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 T is a vertex \(v\) with \(deg_T(v) = 1\).

Proposition 5.11

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

Proof

Our proof is by induction on \(n\). For \(n=2\), there is precisely one tree, which is isomorphic to \(K_2\). Both vertices in this graph are leaves, so the proposition holds for \(n=2\). Now suppose that for some integer \(m \geq 2\), every tree on at most \(m\) vertices has at least two leaves and let \(T=(V,E)\) be a tree on \(m+1\) vertices. Pick an edge \(e \in E\) and form a new graph \(T′=(V′,E′)\) by deleting \(e\) from \(T\). That is, \(V′=V\) and \(E′=E−\{e\}\). Now since \(T′\) does not contain a path from one endpoint of \(e\) to its other endpoint, \(T′\) is not connected. However, deleting an edge cannot create a cycle, so \(T′\) is a forest. Furthermore, it has precisely two components, each of which is a tree with at most m vertices. If each component has at least two vertices, then by induction, each has at least two leaves. In the worst case scenario, two of these leaves are the endpoints of \(e\), so at least two of the vertices are leaves in \(T\), too. If each component of \(T′\) has only one vertex, then \(T≅K_2\), which has two leaves. If exactly one of the components has only one vertex, then it must be a leaf in \(T\). Thus, applying the inductive hypothesis to the other component ensures that there is a second leaf in \(T\).