16.7: Activities

Activity \(\PageIndex{1}\)

1. Draw two different connected graphs with five vertices each in which every edge is a bridge.
2. How many edges are in each of the examples that you drew in Task a?
3. Would it be possible to add an edge to either of the examples that you drew in Task a without creating a cycle?

Activity \(\PageIndex{2}\)

1. Draw two different simple graphs with \(5\) vertices in which every pair of vertices has a single path between them.
2. How many edges are in each of the examples that you drew in Task a?
3. Would it be possible to add an edge to either of the examples that you drew in Task a without creating a cycle?

Activity \(\PageIndex{3}\)

Suppose that \(G\) is a connected graph that consists entirely of a proper cycle. (See Figure \(\PageIndex{1}\).)

Let \(G'\) represent the subgraph of \(G\) that results by removing a single edge. Argue that \(G'\) remains connected.

Activity \(\PageIndex{4}\)

Suppose that \(H\) is a connected graph that contains a proper cycle. Let \(H'\) represent the subgraph of \(H\) that results by removing a single edge from \(H\text{,}\) where the edge removed is part of the proper cycle that \(H\)contains. Argue that \(H'\) remains connected.

Notes.

• Your argument here needs to be (slightly) different from your argument in Activity 16.7.3.
• Make sure you are using the technical definition of connected graph in your argument. What are you assuming about \(H\text{,}\) and what do you need to verify about \(H'\text{?}\)