1.
Take out a piece of paper and draw 8 vertices in a circle.
We are going to add edges to this graph following some requirements.
(a)
First, add the fewest number of edges possible so that the resulting graph is connected. That is, there must be a path between any pair of vertices (a path can use more than one edge, of course).
How many edges are in the graph you drew?
(b)
Was the resulting graph you found a tree?
-
Yes, since the graph is connected and contains no cycles
-
No, the graph contains a cycle
-
No, the graph is not connected
-
No, the graph is not connected and contains a cycle
(c)
Now start over with an empty graph again. This time, add the largest number of edges possible so that the resulting graph contains no cycles.
How many edges are in the graph you drew?
(d)
Was the resulting graph you found a tree?
-
Yes, since the graph is connected and contains no cycles
-
No, the graph contains a cycle
-
No, the graph is not connected
-
No, the graph is not connected and contains a cycle
