14.2: Properties of Graphs

Properties of vertices and edges

Definition: Loop

an edge which connects a vertex to itself

Definition: Parallel Edges

edges which connect the same vertices

Definition: Simple Graph

no loops or parallel edges

Definition: Adjacent Vertices

connected by an edge

Definition: Adjacent Edges

share a common vertex

Definition: Incident

a pair of a vertex and edge where the edge connects the vertex either to itself or another vertex of the graph

Definition: Isolated Vertex

a vertex that is incident with no edges

Definition: Degree(of a vertex)

the number of times that the vertex is incident with an edge of the graph

Definition: \(\text{deg} \; v\)

degree of vertex \(v\)

Note \(\PageIndex{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*} \text{deg} v = \# \{\text{ edges that are incident to } v \text{ but not loops at } v\} + 2 \cdot \# \{\text{ loops at } v\}. \end{equation*}

Example \(\PageIndex{1}\): 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{.}\)

Example \(\PageIndex{2}\): Properties of our slightly more complicated example graph.

The graph of Example 14.1.3 has the following properties.

• It is not a simple graph.
• There are three parallel edges connecting \(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.
• Vertex \(v_4\) is isolated
• For degrees we have

\begin{align*} \text{deg} v_1 & = \text{deg} v_2 = 3, & \text{deg} v_3 & = 4, & \text{deg} v_4 & = 0\text{.} \end{align*}

The number of edges in a graph is an important measure both of how “connected” the graph is, as well as how much “redundancy” the graph contains.

Definition: \(\vert E \vert\)

the number of edges in the graph \(G = (V,E)\)

Theorem \(\PageIndex{1}\): Sum of degrees is twice the number of edges.

Suppose \(G = (V,E)\) is a graph with vertex set \(V = \{ v_1, v_2, \ldots , v_n \}\text{.}\) Then,

\begin{equation*} \text{deg} v_1 + \text{deg} v_2 + \ldots \text{deg} v_n = 2\vert E \vert. \end{equation*}

Proof Idea.

If an edge \(e\) is a loop at vertex \(v_i\text{,}\) then it contributes \(2\) to \(\text{deg} v_i\text{.}\) Otherwise, if edge \(e\) connects vertices \(v_i\) and \(v_j\) (\(v_i \neq v_j\)), then it contributes \(1\) to each of \(\text{deg} v_i\) and \(\text{deg} v_j\text{.}\) In every case, each edge contributes exactly \(2\) to the sum of the vertex degrees.

Corollary \(\PageIndex{1}\): Odd degrees are even.

In every graph, the number of vertices of odd degree is even.

Proof Idea.

Otherwise, the sum of the degrees of all vertices would be odd, which contradicts the theorem above.

Example \(\PageIndex{3}\)

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?

Solution

Create a simple graph with the people at the party as vertices, where two vertices are connected 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.

Subgraphs

Definition: Subgraph

a graph that is a part of a larger graph

Definition: \(G' \preceq G\)

graph \(G'\) is a subgraph of graph \(G\)

Remark

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.5.2.)

Note \(\PageIndex{2}\)

Just as \(\emptyset \subseteq A\) and \(A \subseteq A\) for every set \(A\text{,}\) we consider \((\emptyset,\emptyset) \preceq G\) and \(G \preceq G\) for every graph \(G\text{.}\)

Example \(\PageIndex{4}\)

Determine all possible subgraphs of the graph in Example 14.1.2.

Solution

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

Figure \(\PageIndex{1}\): 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 \(\PageIndex{1}\). There are also \(3\) subgraphs of the fourth and fifth types. Therefore, including the empty graph, there are \(18\) subgraphs of this example graph.

Complete graphs

Definition: Complete Graph

a graph in which every pair of distinct vertices is connected by exactly one edge

Proposition \(\PageIndex{1}\): Properties of complete graphs.

1. Complete graphs are simple.
2. For each \(n \ge 0\text{,}\) there is a unique complete graph \(K_n = (V,E)\) with \(\vert V \vert = n\text{.}\)
3. If \(n \ge 1\text{,}\) then every vertex in \(K_n\) has degree \(n-1\text{.}\)
4. Every simple graph with \(n\) or fewer vertices is a subgraph of \(K_n\text{.}\)

Figure \(\PageIndex{1}\): Complete graphs with \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) and \(6\) vertices.

Checkpoint \(\PageIndex{1}\)

Draw the complete graphs \(K_4\) and \(K_5\text{.}\)

Checkpoint \(\PageIndex{2}\)

Is there a complete graph \(K_0\text{?}\)