# Discrete Mathematics: An Active Approach to Mathematical Reasoning

## Section10.1Graphs

This section focuses on some of the terminology associated with graphs. We will also define some special types of graphs, such as complete graphs.
A graph is a collection of vertices and edges.
Figure 10.1.1 is an example of a graph. We have labeled the vertices with$$v_1, v_2, v_3, v_4$$ and the edges with $$e_1, e_2, e_3, e_4, e_5\text{.}$$

### Definition10.1.2.

A graph, $$G\text{,}$$ consists of a finite set, $$V(G)\text{,}$$ of vertices and a finite set, $$E(G)\text{,}$$ of edges. Each edge is assocated with two vertices (it may be the same vertex) called endpoints.
In the above example, Figure 10.1.1, $$V(G)=\{v_1, v_2, v_3, v_4\}, E(G)=\{e_1, e_2, e_3, e_4, e_5\}\text{.}$$ The endpoints of edge $$e_1$$ are $$v_1, v_2\text{.}$$
If two edges have the same endpoints, we say they are parallel.
A loop is an edge where both endpoints are the same vertex.
Two vertices connected by an edge are called adjacent. For example, in Figure 10.1.1 $$v_2$$ is adjacent to $$v_3\text{,}$$ but $$v_3$$ is not adjacent to $$v_4\text{.}$$
A vertex of a loop is adjacent to itself.
An edge is incident on each of its endpoints.
Two edges that are incident on the same vertex are adjacent. For example, in Figure 10.1.1 $$e_1$$ and $$e_2$$ are adjacent, but $$e_2$$ and $$e_5$$ are not adjacent.
An isolated vertex is one with no incident edges.
A graph with no vertices is the empty graph.
In Figure 10.1.3, edges $$e_1$$ and $$e_2$$ are parallel edges, while edge $$e_3$$ is a loop. We also have an isolated vertex, $$v_3\text{.}$$

### Example10.1.4.Graph Terminology.

Consider the graph, $$G$$ given in the figure.
Find $$V(G)\text{.}$$
$$V(G)=\{v_1, v_2, v_3, v_4\}$$
Find $$E(G)\text{.}$$
$$E(G)=\{e_1, e_2, \ldots, e_6\}$$
Find the endpoints for $$e_1\text{.}$$
$$\{v_1, v_2\}$$
Find the endpoints for $$e_3\text{.}$$
$$\{v_1, v_3\}$$
Find the endpoints for $$e_6\text{.}$$
$$\{v_3, v_4\}$$
Find the edges incident on $$v_1\text{.}$$
$$e_1, e_2, e_3, e_4$$
Find all vertices adjacent to $$v_4\text{.}$$
$$\{v_1, v_3\}$$
Does $$G$$ have any parallel edges?
Yes. $$e_2, e_3$$
Does $$G$$ have any loops?
No.
It is important to note that it is possible to draw the same graph in different ways.
The two graphs in Figure 10.1.6 are the same graph since they have the same vertex and edge sets, and a given edge still has the same endpoints.

### Definition10.1.7.

A directed graph or digraph consists of a set of vertices, $$V(G)$$ and directed edges (arrows), $$D(G)\text{,}$$ where each edge is associated with an ordered pair of of vertices called endpoints, $$(v, w)\text{.}$$
We saw directed graphs in Section 8.1 and Section 8.2. For example, see Figure 8.1.10. In this example, we have an edge with endpoints $$(1, 2)\text{,}$$ but not $$(2, 1)\text{.}$$
Really, the vertices of a graph represent a set, while the edges represent relationships between elements of that set. There are lots of examples of graphs as representations of relationships or networks. For example, graphs are used to represent communications systems, flight patterns, and friendship networks. Graphs can even be used to find strategies in games such as sudoku.
A graph with no parallel edges or loops is called simple. For example, Figure 10.1.1 is simple, while Figure 10.1.3 is not.
Now we want to define a couple special graphs.

### Definition10.1.8.

A complete graph on $$n$$ vertices, $$K_n\text{,}$$ is a simple graph with $$n$$ vertices whose set of edges contains exactly one edge for every pair of vertices.
$$K_1, \ldots, K_4$$ are given in the following figure.

### Activity10.1.1.

Draw the complete graphs on 5 vertices and 6 vertices, $$K_5$$ and $$K_6\text{.}$$

### Definition10.1.10.

Let $$m, n\in \mathbb{Z}^{+}\text{.}$$ A complete bipartite graph on $$(m, n)$$ vertices, $$K_{m, n}\text{,}$$ is a simple graph with vertices $$v_1, v_2, \ldots, v_m$$ and $$w_1, w_2, \ldots w_n\text{,}$$ such that
1. there is an edge from $$v_i$$ to $$w_j$$ for all $$i=1, \ldots, m$$ and $$j=1, \ldots n\text{;}$$
2. there are no edges from $$v_i$$ to $$v_k$$ for all $$i, k=1, \ldots, m\text{;}$$
3. there are no edges from $$w_i$$ to $$w_k$$ for all $$i, k=1, \ldots, n\text{.}$$

### Activity10.1.2.

Draw the complete bipartite graphs $$K_{3, 3}$$ and $$K_{4, 5}\text{.}$$

### Definition10.1.12.

A graph $$H$$ is a subgraph of $$G$$ if every vertex in $$H$$ is also a vertex in $$G\text{,}$$ and every edge in $$H$$ is also an edge in $$G$$ such that the edges in $$H$$ have the same endpoints as in $$G\text{.}$$
In the following figure, $$H_1$$ and $$H_2$$ are subgraphs of $$G\text{.}$$

### Definition10.1.14.

The degree of a vertex $$v\text{,}$$ $$\text{deg}(v)\text{,}$$ is the number of edges incident on $$v\text{.}$$ Loops are counted twice. The total degree of a graph $$G$$ is the sum of the degrees of all vertices in $$G\text{.}$$

### Example10.1.15.Degree.

Let $$G$$ be the graph in Figure 10.1.1.
Find $$\text{deg}(v_2)\text{.}$$
3
Find $$\text{deg}(v_4)\text{.}$$
2
Find the total degree of $$G\text{.}$$
10
Let $$G$$ be the graph in Figure 10.1.3.
Find $$\text{deg}(v_2)\text{.}$$
4
Find $$\text{deg}(v_3)\text{.}$$
0
Find the total degree of $$G\text{.}$$
6
Is there a relationship between the number of edges in $$G$$ and the total degree?
As you might have seen in Example 10.1.15, there is a relationship between the total degree of a graph and the number of edges.
We will not provide a formal proof, but the theorem is not hard to show as each edge must be incident on two vertices. Thus, each edge is counted twice in the total degree.

### Activity10.1.3.

Draw any graph with 6 edges. Find the total degree of your graph. Verify that the total degree is twice the number of edges.

### Activity10.1.4.

Explain why in any graph there is an even number of vertices of odd degree.

### Activity10.1.5.

For each of the following either draw an example of the graph or explain why it is impossible.

#### (a)

A graph with 4 vertices of degrees 1, 1, 2, 3.

#### (b)

A graph with 4 vertices of degrees 1, 1, 2, 2.

#### (c)

A simple graph with 4 vertices of degrees 1, 1, 2, 2.

#### (d)

A graph with 4 vertices of degrees 1, 2, 3, 3.

#### (e)

A simple graph with 4 vertices of degrees 1, 2, 3, 4.

#### (f)

A simple graph with 6 edges and all vertices of degrees 3.

Use the following graph for questions about $$G\text{.}$$

#### 1.

List the edges of $$G\text{,}$$ Figure 10.1.18, incident on $$v_2\text{.}$$
Hint.
There are 5 edges.

#### 2.

True or false $$G\text{,}$$ Figure 10.1.18, has parallel edges.
• True.

• Edges $$e_3, e_6$$ are parallel.
• False.

• Edges $$e_3, e_6$$ are parallel.

#### 3.

True or false: in $$G\text{,}$$ Figure 10.1.18, $$v_1$$ and $$v_2$$ are adjacent.
• True.

• False.

#### 4.

True or false: in $$G\text{,}$$ Figure 10.1.18, $$v_3$$ and $$v_4$$ are adjacent.
• True.

• False.

#### 5.

True or false: in $$G\text{,}$$ Figure 10.1.18, $$e_3$$ and $$e_6$$ are adjacent.
• True.

• False.

#### 6.

In $$G\text{,}$$ Figure 10.1.18, find the degree of $$v_4\text{.}$$

#### 7.

In $$G\text{,}$$ Figure 10.1.18, find the degree of $$v_2\text{.}$$

#### 8.

What is the total degree of $$G\text{,}$$ Figure 10.1.18?

#### 9.

Draw $$K_5\text{.}$$ How many edges does it have?
What is the degree of each vertex?

#### 10.

True or false: there exists a graph with 4 vertices of degrees 1, 2, 1, 2.
• True.

• One example is a line (path) with 4 vertices.
• False.

• One example is a line (path) with 4 vertices.

#### 11.

True or false: there exists a graph with 4 vertices of degrees 1, 2, 1, 3.
• True.

• The total degree would be odd.
• False.

• The total degree would be odd.

#### 12.

True or false: there exists a graph with 4 vertices of degrees 4, 4, 4, 4.
• True.

• One example has parallel edges between each vertex. Can also have an example with loops.
• False.

• One example has parallel edges between each vertex. Can also have an example with loops.

#### 13.

True or false: there exists a simple graph with 4 vertices of degrees 4, 4, 4, 4.
• True.

• In a simple graph, you can’t have more edges than the complete graph on 4 vertices.
• False.

• In a simple graph, you can’t have more edges than the complete graph on 4 vertices.

### ExercisesExercises

#### 1.

Draw the graph given by the following information: Graph $$H$$ has vertex set $$\{v_1, v_2, v_3, v_4, v_5\}$$ and edge set $$\{e_1, e_2, e_3, e_4\}$$ with edge-endpoint function given by the table.
Edge Endpoints
$$e_1$$ $$\{v_1\}$$
$$e_2$$ $$\{v_2, v_3\}$$
$$e_3$$ $$\{v_2, v_3\}$$
$$e_4$$ $$\{v_1, v_5\}$$

#### 2.

Show that the two drawings represent the same graph by labeling the vertices and edges of the right-hand drawing to correspond to those of the left-hand drawing.

#### 3.

Show that the two drawings represent the same graph by labeling the vertices and edges of the right-hand drawing to correspond to those of the left-hand drawing.

#### 4.

Consider the graph
1. Find all edges that are incident on $$V_1\text{.}$$
2. Find all vertices that are adjacent to $$v_3\text{.}$$
3. Find all edges that are adjacent to $$e_1\text{.}$$
4. Find all loops.
5. Find all parallel edges.
6. Find all isolated vertices.
7. Find the degree of $$v_3\text{.}$$
8. Find the total degree of the graph.

#### 5.

A graph has vertices of degrees 0, 2, 2, 3, and 9. How many edges does the graph have?

#### 6.

For each of the following, draw the graph if it exists or explain why no such graph exists.
1. A graph with four vertices of degrees 1, 1, 1, and 4.
2. A graph with four vertices of degrees 1, 2, 3, and 4.
3. A simple graph with 9 edges and all vertices of degree 3.

#### 7.

In a group of 25 people, is it possible for each person to shake hands with exactly 3 other people? Explain your answer.

#### 8.

Recall that $$K_{m,n}$$ denotes the complete bipartite graph on $$(m, n)$$ vertices.
1. Draw $$K_{4, 2}\text{.}$$
2. Draw $$K_{1, 3}\text{.}$$
3. Draw $$K_{3, 4}\text{.}$$
4. How many vertices of $$K_{m, n}$$ have of degree $$m\text{?}$$ degree $$n\text{?}$$
5. What is the total degree of $$K_{m, n}\text{?}$$
6. Find a formula in terms of $$m$$ and $$n$$ for the number of edges of $$K_{m, n}\text{.}$$

#### 9.

Recall $$K_n$$ is the complete graph on $$n$$ vertices.
1. Draw $$K_6\text{.}$$
2. Show that for all integers $$n\geq 1\text{,}$$ the number of edges of $$K_n$$ is $$\frac{n(n-1)}{2}\text{.}$$
Hint.
There are two possible approaches for the proof. One is to try a counting argument, the other is to do induction on $$n\text{.}$$