a pair of a vertex and edge where the edge links that vertex either to itself or another vertex of the graph
loop
an edge which links a vertex to itself
parallel edges
edges which link the same vertices
simple graph
no loops or parallel edges
isolated vertex
a vertex that is incident with no edges
degree (of a vertex)
the number of times that the vertex is incident with an edge of the graph
\(\deg v\)
degree of vertex \(v\)
Note14.2.1.
In a simple graph, the degree of each vertex is equal to the number of incident edges. However, in a non-simple graph, a loop is incident to its vertex twice, and we count that in the degree:
\begin{equation*}
\deg v
= \ncardop \{\text{ edges that are incident to } v \text{ but not loops at } v\}
+ 2 \cdot \ncardop \{\text{ loops at } v\}.
\end{equation*}
Example14.2.2.Properties of our very basic example graph.
The graph of Example 14.1.2 has the following properties.
It is a simple graph.
Each pair of vertices is adjacent.
Each pair of edges is adjacent but not parallel.
There are no loops.
Each vertex is incident to two non-loop edges, so each vertex has degree \(2\text{.}\)
Example14.2.3.Properties of our slightly more complicated example graph.
The graph of Example 14.1.4 has the following properties.
It is not a simple graph.
There are three parallel edges linking \(v_1\) and \(v_2\text{.}\)
There are two loops at vertex \(v_3\) (and these are also parallel edges).
The parallel edges between \(v_1\) and \(v_2\) are adjacent, as are the two loops at \(v_3\text{.}\)
Vertices \(v_1\) and \(v_2\) are adjacent, and vertex \(v_3\) is adjacent to itself.
Vertices \(v_1\) and \(v_2\) are incident to the three edges running between them, and vertex \(v_3\) is incident to its two loops.
If an edge \(e\) is a loop at vertex \(v_i\text{,}\) then it contributes \(2\) to \(\deg v_i\text{.}\) Otherwise, if edge \(e\) links vertices \(v_i\) and \(v_j\) (\(v_i \neq v_j\)), then it contributes \(1\) to each of \(\deg v_i\) and \(\deg v_j\text{.}\) In every case, each edge contributes exactly \(2\) to the sum of the vertex degrees.
Corollary14.2.5.Odd degrees are even.
In every graph, the number of vertices of odd degree is even.
Otherwise, the sum of the degrees of all vertices would be odd, which contradicts the theorem above.
Worked Example14.2.6.
An odd fellow throws an odd party and invites an even number of other equally-odd people. Each odd person at the party is friends with an odd number of other odd people at the party. Is this odd party even possible?
Create a simple graph with the people at the party as vertices, where two vertices are linked by a single edge if and only if the two people are friends. As each person has an odd number of friends at the party, the degree of each vertex is odd. But the number of party attendees is also odd, since there are an even number of invitees, plus the host himself. So we have an odd number of vertices each with odd degree, which the corollary above says is not possible.
Subsection14.2.2Subgraphs
subgraph
a graph that is a part of a larger graph
\(G' \subgraph G\)
graph \(G'\) is a subgraph of graph \(G\)
Remark14.2.7.
Without a diagram, how can we tell if a graph \(G' = (V',E')\) is a subgraph of another graph \(G = (V,E)\text{?}\) First, each vertex of \(G'\) should also be a vertex of \(G\text{,}\) so that \(V' \subseteq V\text{.}\) And also, each edge of \(G'\) should also appear as an edge in \(G\text{.}\) (Though we shouldn’t just write \(E' \subseteq E\text{,}\) and not only because \(E'\) and \(E\) are actually sets — see Activity 14.2.)
Note14.2.8.
Just as \(\emptyset \subseteq A\) and \(A \subseteq A\) for every set \(A\text{,}\) we consider \((\emptyset,\emptyset) \subgraph G\) and \(G \subgraph G\) for every graph \(G\text{.}\)
Worked Example14.2.9.
Determine all possible subgraphs of the graph in Example 14.1.2.
First, every graph contains the empty graph as a subgraph. Next, a nonempty subgraph of this particular graph can contain one, two, or all three vertices. We can write out all nonempty possibilities in a general way based on the number of vertices in the subgraph. In each graph below we require the vertex indices \(i, j, k\) to all be distinct and to satisfy \(1 \le i,j,k \le 3\text{.}\)
Figure14.2.10.All possible subgraphs of our basic example graph from Example 14.1.2.
There are \(3\) subgraphs of each of the first three types in Figure 14.2.10. There are also \(3\) subgraphs of the fourth and fifth types. Therefore, including the empty graph, there are \(18\) subgraphs of this example graph.
Subsection14.2.3Complete graphs
complete graph
a simple graph in which every pair of distinct vertices is adjacent
Proposition14.2.11.Properties of complete graphs.
For each \(n \ge 0\text{,}\) there is a unique complete graph \(K_n = (V,E)\) with \(\card{V} = n\text{.}\)
If \(n \ge 1\text{,}\) then every vertex in \(K_n\) has degree \(n-1\text{.}\)
Every simple graph with \(n\) or fewer vertices is a subgraph of \(K_n\text{.}\)
(a)\(K_1\text{.}\)
(b)\(K_2\text{.}\)
(c)\(K_3\text{.}\)
(d)\(K_6\text{.}\)
Figure14.2.12.Complete graphs with \(1\text{,}\)\(2\text{,}\)\(3\text{,}\) and \(6\) vertices.
Checkpoint14.2.13.
Draw the complete graphs \(K_4\) and \(K_5\text{.}\)
