Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Activities 15.5 Activities
A4US

🔗

Activity 15.1.

🔗
In each of the following, devise a graph that contains the requested type of walk. (You do not need to create one graph that contains all three types of walks; you may draw three separate graphs.)
🔗

(a)

🔗
A closed path that is not a trail.
🔗

(b)

🔗
An open trail that is not a path.
🔗

(c)

🔗
A closed trail that is not a path.
🔗

Activity 15.2.

🔗
Devise a graph with exactly four vertices, each of which has degree 5, so that the graph is
🔗

Activity 15.3.

🔗
In each of the following, devise a connected graph with at least five vertices that has the requested properties. Do so without looking at the example graphs in this chapter. (You do not need to create one graph that contains all of the properties; you may draw a separate graph for each task below.)
🔗

(c)

🔗
Contains an articulation vertex.
🔗

(d)

🔗
Every vertex of degree at least 2 is an articulation vertex.
🔗

Activity 15.4.

🔗
Does increasing the number of edges in a graph increase its edge connectivity?
🔗

Activity 15.5.

A nonconnected graph.
Figure 15.5.1. A nonconnected graph.
🔗
In the graph of Figure 15.5.1, explain why the subgraph formed by vertices 2, 3, and 4, along with all edges incident to these vertices, fails the formal definition of connected component. Identify which of the two conditions of this formal definition the subgraph fails, and explicitly describe how the subgraph fails to meet that condition.
🔗

Activity 15.6.

🔗
Suppose G is a simple, nonconnected graph with n vertices that is maximal with respect to these properties. That is, if you tried to make a larger graph in which G is a subgraph, this larger graph will lose at least one of the properties (a) simple, (b) nonconnected, or (c) has n vertices.
🔗
What does being maximal with respect to these properties imply about G? That is, what further properties must G possess because of this assumption?
🔗

Activity 15.7.

🔗
An Euler circuit is a closed trail in a connected graph G that traverses every edge of G. Since it must be a trail, you could say that an Euler circuit traverses each edge of G exactly once (as well as ending at the same node at which it begins).
🔗
Prove that if a connected graph contains an Euler circuit, then every vertex in that graph must have even degree.
<Prev^TopNext>