Graphs

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.

🔗

4.

Consider the graph

🔗

Find all edges that are incident on $V_{1} .$
🔗

🔗
Find all vertices that are adjacent to $v_{3} .$
🔗

🔗
Find all edges that are adjacent to $e_{1} .$
🔗

🔗
Find all loops.
🔗

🔗
Find all parallel edges.
🔗

🔗
Find all isolated vertices.
🔗

🔗
Find the degree of $v_{3} .$
🔗

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

🔗
Draw $K_{1, 3} .$
🔗

🔗
Draw $K_{3, 4} .$
🔗

🔗
How many vertices of $K_{m, n}$ have of degree $m ?$ degree $n ?$
🔗

🔗
What is the total degree of $K_{m, n} ?$
🔗

🔗
Find a formula in terms of $m$ and $n$ for the number of edges of $K_{m, n} .$
🔗

🔗

🔗

9.

Recall

K_{n}

is the complete graph on

n

vertices.

🔗

Draw $K_{6} .$
🔗

🔗
Show that for all integers $n \geq 1,$ the number of edges of $K_{n}$ is $\frac{n (n - 1)}{2} .$
🔗

🔗

Hint.

There are two possible approaches for the proof. One is to try a counting argument, the other is to do induction on

n .

🔗

You have attempted 1 of 14 activities on this page.

🔗

Prev Top Next