EF Exercises

Skip to main content

Exercises 14.6 Exercises

An example graph. — 🔗
Figure 14.6.1. An example graph.

1.

Consider the graph in Figure 14.6.1.

(a)

Are vertices 1 and 2 incident?

(b)

Are any vertices adjacent to themselves?

(c)

Is vertex 3 adjacent to vertex 6?

(d)

Is this a simple graph?

(e)

Compute the degree of each vertex in the graph. Then verify that the sum of the degrees is equal to twice the number of edges. (See Theorem 14.2.4.)

2.

(a)

How many edges does the complete graph with ten vertices have?

See Theorem 14.2.4.

(b)

Generalize your result to a formula for the number of edges in the complete graph with

n

vertices.

3.

(a)

Draw an example of a simple graph that has no vertices of odd degree.

(b)

Draw an example of a simple graph that has no vertices of even degree.

4.

Given a collection of sets

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

the intersection graph of the collection is the simple graph that has a vertex for each of the sets in the collection, with two vertices joined by an edge if and only if the two corresponding sets have nonempty intersection. Draw the intersection graph of the following collection of sets.

\begin{matrix} A_{1} = {1, 2, 3, 4, 5}, \\ A_{2} = {2, 4, 6, 8}, \\ A_{3} = {3, 5, 12}, \\ A_{4} = {5, 8, 10} . \end{matrix}

Complement of a graph.

Exercises 5–7 concern the following definition.

complement (of a simple graph $G$ ): 🔗
the simple graph that has the same vertex set as $G,$ but in which two vertices are joined by an edge if and only if those same two vertices are not joined by an edge in $G$

5.

Draw the complement of the simple graph in Figure 14.6.2.

A simple graph. — Figure 14.6.2. A simple graph.

6.

What is the complement of a complete graph?

7.

Suppose

G

is a simple graph with

n

vertices. Determine a relationship between the number of edges in

G,

the number of edges in the complement of

G,

and the number of edges in the complete graph

K_{n}

with

n

vertices.

Recall that every simple graph with

n

vertices is a subgraph of

K_{n} .

<Prev ^Top Next>