Definition 10.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.
Section 10.1 Graphs
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{.}\)
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{.}\)
Example 10.1.4. Graph Terminology.
Consider the graph, \(G\) given in the figure.
Find \(V(G)\text{.}\)
Answer 1.
\(V(G)=\{v_1, v_2, v_3, v_4\}\)
Find \(E(G)\text{.}\)
Answer 2.
\(E(G)=\{e_1, e_2, \ldots, e_6\}\)
Find the endpoints for \(e_1\text{.}\)
Answer 3.
\(\{v_1, v_2\}\)
Find the endpoints for \(e_3\text{.}\)
Answer 4.
\(\{v_1, v_3\}\)
Find the endpoints for \(e_6\text{.}\)
Answer 5.
\(\{v_3, v_4\}\)
Find the edges incident on \(v_1\text{.}\)
Answer 6.
\(e_1, e_2, e_3, e_4\)
Find all vertices adjacent to \(v_4\text{.}\)
Answer 7.
\(\{v_1, v_3\}\)
Does \(G\) have any parallel edges?
Answer 8.
\(e_2, e_3\)
Does \(G\) have any loops?
Answer 9.
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.
Definition 10.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.
Definition 10.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.
Activity 10.1.1.
Draw the complete graphs on 5 vertices and 6 vertices, \(K_5\) and \(K_6\text{.}\)
Definition 10.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
- there is an edge from \(v_i\) to \(w_j\) for all \(i=1, \ldots, m\) and \(j=1, \ldots n\text{;}\)
- there are no edges from \(v_i\) to \(v_k\) for all \(i, k=1, \ldots, m\text{;}\)
- there are no edges from \(w_i\) to \(w_k\) for all \(i, k=1, \ldots, n\text{.}\)
Activity 10.1.2.
Draw the complete bipartite graphs \(K_{3, 3}\) and \(K_{4, 5}\text{.}\)
Definition 10.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{.}\)
Definition 10.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{.}\)
Example 10.1.15. Degree.
Let \(G\) be the graph in Figure 10.1.1.
Find \(\text{deg}(v_2)\text{.}\)
Answer 1.
Find \(\text{deg}(v_4)\text{.}\)
Answer 2.
Find the total degree of \(G\text{.}\)
Answer 3.
Let \(G\) be the graph in Figure 10.1.3.
Find \(\text{deg}(v_2)\text{.}\)
Answer 4.
Find \(\text{deg}(v_3)\text{.}\)
Answer 5.
Find the total degree of \(G\text{.}\)
Answer 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.
Theorem 10.1.16.
The total degree of a graph \(G\) is \(2k\) where \(k\) is the number of edges in \(G\text{.}\)
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.
Activity 10.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.
Corollary 10.1.17.
The total degree of any graph is even.
Activity 10.1.4.
Explain why in any graph there is an even number of vertices of odd degree.
Activity 10.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.
Reading Questions Check Your Understanding
Use the following graph for questions about \(G\text{.}\)
1.
Hint.
There are 5 edges.
2.
True.
- Edges \(e_3, e_6\) are parallel.
False.
- Edges \(e_3, e_6\) are parallel.
True or false \(G\text{,}\) Figure 10.1.18, has parallel edges.
3.
True.
False.
4.
True.
False.
5.
True.
False.
6.
7.
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.
- One example is a line (path) with 4 vertices.
False.
- One example is a line (path) with 4 vertices.
True or false: there exists a graph with 4 vertices of degrees 1, 2, 1, 2.
11.
True.
- The total degree would be odd.
False.
- The total degree would be odd.
True or false: there exists a graph with 4 vertices of degrees 1, 2, 1, 3.
12.
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.
True or false: there exists a graph with 4 vertices of degrees 4, 4, 4, 4.
13.
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.
True or false: there exists a simple graph with 4 vertices of degrees 4, 4, 4, 4.
Exercises Exercises
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
- Find all edges that are incident on \(V_1\text{.}\)
- Find all vertices that are adjacent to \(v_3\text{.}\)
- Find all edges that are adjacent to \(e_1\text{.}\)
- Find all loops.
- Find all parallel edges.
- Find all isolated vertices.
- Find the degree of \(v_3\text{.}\)
- 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.
- A graph with four vertices of degrees 1, 1, 1, and 4.
- A graph with four vertices of degrees 1, 2, 3, and 4.
- 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.
- Draw \(K_{4, 2}\text{.}\)
- Draw \(K_{1, 3}\text{.}\)
- Draw \(K_{3, 4}\text{.}\)
- How many vertices of \(K_{m, n}\) have of degree \(m\text{?}\) degree \(n\text{?}\)
- What is the total degree of \(K_{m, n}\text{?}\)
- 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.
- Draw \(K_6\text{.}\)
- 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{.}\)
You have attempted of activities on this page.
