Definition 3.2.1.
A graph \(G\text{,}\) also called a network, consists of a finite set \(V=V(G)\) called the vertices or nodes of \(G\) and a collection \(E=E(G)\) of unordered pairs of elements of \(V\) called the edges or arcs of \(G\text{.}\)
Section 3.2 Graphs and Networks
Many stuctures in the world involve pairwise connections. For example, in a group of people, we could connect each pair of people who are friends. In a city and road network, we can consider two cities connected if there is a road connecting them without any other cities on that road. In a computer network, two computers can be considered connected if they have a direct cable link between them, without any intermediary system.
The mathematical structure that captures the structure of pairwise connection is a graph, also called a network.
Example 3.2.2.
The complete graph, denoted \(K_n\text{,}\) is the graph with \(V=[n]\) and every possible edge. Thus, \(K_n\) has \(n\) vertices and \(\binom{n}{2}\) edges.
Example 3.2.4.
The Petersen graph is a famous and important graph shown in the figure below. The Petersen graph is particularly noteworthy because it is often a counterexample to conjectures about graphs; if you think something is true, always test your guess on the Petersen graph!
Definition 3.2.6.
For a vertex \(v\in V(G)\text{,}\) we say the degree of \(v\) is the number of edges in \(E(G)\) that contain \(v\text{.}\) We denote the degree of a vertex by \(\deg_G(v)\text{,}\) where we will write \(\deg(v)\) if \(G\) is clear from context.
Checkpoint 3.2.7.
Find the degree of each vertex in the graph below:
The first key result regarding graphs is the following.
Theorem 3.2.9.
Given a graph \(G=(V,E)\text{,}\) we have
\begin{equation*}
\sum_{v\in V}\deg(v)=2|E| \, .
\end{equation*}
Proof.
We count the number of pairs \((v,e)\) where \(v\in e\in E\) in two ways. This is a strategy called "double counting". First, for each edge, there are two pairs \((v,e)\text{,}\) one for each endpoint \(v\) of the edge. Thus, the total number of pairs is \(2|E|\text{.}\)
Second, for each vertex, there are \(\deg(v)\) pairs \((v,e)\text{,}\) one for each edge \(e\) containing \(v\text{.}\) Thus, there are a total of \(\sum_{v\in V}\deg(v)\) such pairs. Since both of these expressions count the same set, they are equal.
Checkpoint 3.2.10.
Discuss this proof. Does it make sense? Does it make sense why we call this type of proof "double counting"?
We can use the result above to prove a fundamental qualitative result about graphs: the handshake lemma.
Theorem 3.2.11. Handshake Lemma.
In any finite graph, there are an even number of vertices of odd degree.
Proof.
Since \(\sum_{v\in V}\deg(v)=2|E|\text{,}\) the sum of the degrees is an even number. If there were an odd number of vertices of odd degree, the sum would be odd, which is impossible.
The handshake lemma allows us to obtain statements such as the following.
Corollary 3.2.12.
If every vertex of a graph has odd degree, then the graph has an even number of vertices.
Note that the theorem and corollary above do not tell us anything about how many vertices there are, or how many odd degree vertices there are. So, this is not a theorem or corollary that we can use to count with. However, these results do tell us qualitative information about the relationship between the degrees of a graph, the total number of edges, and limitations on the number of vertices of odd degree.
Another quality of a graph is whether or not it is connected, where by connected we mean the following.
Definition 3.2.13.
Given a graph \(G\text{:}\)
-
A path is a finite sequence of edges joining a sequence of vertices.
-
A trail is a path in which all edges are distinct.
-
A simple path is a path in which all vertices are distinct.
-
A circuit is a trail in which the first and last vertices are equal.
-
A cycle is a trail in which only the first and last vertices are equal. A cycle with \(k\) edges is called a \(k\)-cycle.
-
A graph is connected if there is a path between every pair of vertices.
Checkpoint 3.2.14.
Below are examples of a connected and disconnected graph. In the connected graph, for each of the following sequences of vertices, identify which are a path, trail, simple path, circuit, or cycle.
-
\(\displaystyle 0,6,5,4,0\)
-
\(\displaystyle 1,3,0,6,8\)
-
\(\displaystyle 1,3,0,6,5,4,0,9\)
-
\(\displaystyle 1,3,0,6,0,9\)
-
\(\displaystyle 0,3,2,10,9,0,4,5,6,0\)
There are algorithms known that will generate all connected graphs on a fixed number of vertices, but these are difficult. The number of connected graphs, with vertices that are not labeled, on \(n\) vertices for \(n\geq 1\) is \(1, 1, 2, 6, 21, 112, 853, 11117, 261080,\ldots\text{,}\) and more information can be found in the Online Encyclopedia of Integer Sequences:
https://oeis.org/A001349
