Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Exercises 15.6 Exercises

🔗

Recognizing paths and trails.

🔗
In each of Exercises 1–4, you are given a walk through a graph. Determine whether the walk is a path, a trail, or neither. Also determine whether the walk is open or closed.
🔗

1.

🔗
v1,e1,v2,e2,v3,e3,v4,e12,v6,e6,v3.
🔗

2.

🔗
v1,e1,v2,e2,v3,e3,v4,e4,v5,e5,v6,e6,v3,e7,v7,e8,v1.
🔗

5.

🔗
Consider the graph in Figure 15.6.1.
An example graph for an exercise.
Figure 15.6.1. An example graph.
🔗

(a)

🔗
Determine four different paths from vertex 1 to vertex 5.
🔗

(b)

🔗
Determine four different trails from vertex 1 to vertex 5, none of which are paths.
🔗

(c)

🔗
Determine four different walks from vertex 1 to vertex 5, none of which are trails.
🔗

6.

🔗
Consider the graph in Figure 15.6.2.
An example graph for an exercise.
Figure 15.6.2. An example graph.
🔗

(a)

🔗
How many different trails are there from vertex 1 to vertex 5?
🔗

(c)

🔗
How many different walks are there from vertex 1 to vertex 5?
🔗

Recognizing bridges.

🔗
In each of Exercises 7–10, identify each edge that is a bridge.
🔗

10.

🔗
The complete graph with n vertices.
🔗

11.

🔗
Among all possible nonconnected graphs with n vertices, let H be one with the maximum number of edges. Prove that H has exactly two connected components.
Hint.
Argue by contradiction.
🔗

12.

🔗
Suppose G is a connected graph that contains a closed path that is also a trail. Prove that it is possible to remove any single edge from this path and be left with a connected subgraph of G. That is, prove that no edge in this path could be a bridge.
🔗

13.

🔗
Prove that a graph in which every edge is a bridge cannot have a closed path that is also a trail.
<Prev^TopNext>