Graphs

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. Example of a graph, $G$
🔗

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} .

🔗

Definition 10.1.2.

A graph,

G,

consists of a finite set,

V (G),

of vertices and a finite set,

E (G),

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}} .

The endpoints of edge

e_{1}

are

v_{1}, v_{2} .

🔗

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},

but

v_{3}

is not adjacent to

v_{4} .

🔗

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} .

🔗

Figure 10.1.3. Example of a graph with parallel edges and a loop
🔗

Example 10.1.4. Graph Terminology.

Consider the graph,

G

given in the figure.

Find

V (G) .

Answer 1.

V (G) = {v_{1}, v_{2}, v_{3}, v_{4}}

Find

E (G) .

Answer 2.

E (G) = {e_{1}, e_{2}, \dots, e_{6}}

Find the endpoints for

e_{1} .

Answer 3.

{v_{1}, v_{2}}

Find the endpoints for

e_{3} .

Answer 4.

{v_{1}, v_{3}}

Find the endpoints for

e_{6} .

Answer 5.

{v_{3}, v_{4}}

Find the edges incident on

v_{1} .

Answer 6.

e_{1}, e_{2}, e_{3}, e_{4}

Find all vertices adjacent to

v_{4} .

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.

🔗

Figure 10.1.6. The same graph drawn in two 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),

where each edge is associated with an ordered pair of of vertices called endpoints,

(v, w) .

🔗

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),

but not

(2, 1) .

🔗

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},

is a simple graph with

n

vertices whose set of edges contains exactly one edge for every pair of vertices.

🔗

K_{1}, \dots, K_{4}

are given in the following figure.

🔗

Figure 10.1.9. Examples of complete graphs
🔗

Activity 10.1.1.

Draw the complete graphs on 5 vertices and 6 vertices,

K_{5}

and

K_{6} .

🔗

Definition 10.1.10.

Let

m, n \in Z^{+} .

A complete bipartite graph on

(m, n)

vertices,

K_{m, n},

is a simple graph with vertices

v_{1}, v_{2}, \dots, v_{m}

and

w_{1}, w_{2}, \dots w_{n},

such that

🔗

there is an edge from $v_{i}$ to $w_{j}$ for all $i = 1, \dots, m$ and $j = 1, \dots n;$
there are no edges from $v_{i}$ to $v_{k}$ for all $i, k = 1, \dots, m;$
there are no edges from $w_{i}$ to $w_{k}$ for all $i, k = 1, \dots, n .$

🔗

Figure 10.1.11. Complete bipartite graph, $K_{3, 2}$
🔗

Activity 10.1.2.

Draw the complete bipartite graphs

K_{3, 3}

and

K_{4, 5} .

🔗

Definition 10.1.12.

A graph

H

is a subgraph of

G

if every vertex in

H

is also a vertex in

G,

and every edge in

H

is also an edge in

G

such that the edges in

H

have the same endpoints as in

G .

🔗

In the following figure,

H_{1}

and

H_{2}

are subgraphs of

G .

🔗

Figure 10.1.13. Examples of subgraphs, $H_{1}, H_{2},$ of the graph $G$
🔗

Definition 10.1.14.

The degree of a vertex

v,

deg (v),

is the number of edges incident on

v .

Loops are counted twice. The total degree of a graph

G

is the sum of the degrees of all vertices in

G .

🔗

Example 10.1.15. Degree.

Let

G

be the graph in Figure 10.1.1.

Find

deg (v_{2}) .

Answer 1.

Find

deg (v_{4}) .

Answer 2.

Find the total degree of

G .

Answer 3.

Let

G

be the graph in Figure 10.1.3.

Find

deg (v_{2}) .

Answer 4.

Find

deg (v_{3}) .

Answer 5.

Find the total degree of

G .

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

2 k

where

k

is the number of edges in

G .

🔗

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 .

🔗

Figure 10.1.18. The graph $G$ for Check Your Understanding
🔗

1.

List the edges of

G,

Figure 10.1.18, incident on

v_{2} .

🔗

Hint.

There are 5 edges.

🔗

2.

True or false

G,

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,

Figure 10.1.18,

v_{1}

and

v_{2}

are adjacent.

🔗

True.
False.

🔗

4.

True or false: in

G,

Figure 10.1.18,

v_{3}

and

v_{4}

are adjacent.

🔗

True.
False.

🔗

5.

True or false: in

G,

Figure 10.1.18,

e_{3}

and

e_{6}

are adjacent.

🔗

True.
False.

🔗

6.

G,

Figure 10.1.18, find the degree of

v_{4} .

🔗

7.

G,

Figure 10.1.18, find the degree of

v_{2} .

🔗

8.

What is the total degree of

G,

Figure 10.1.18?

🔗

9.

Draw

K_{5} .

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.

🔗

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.

🔗