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