Discrete Mathematics for Computer Science

Exercises 367

W Exercises

1. Construct connected graphs of the following sorts:
   (a) All graphs of five vertices with at least seven edges
   (b) All cubic graphs with at most eight vertices
   (c) One 4-regular graphs of six vertices
   (d) Three 5-regular graphs of eight vertices


2. In a graph, the edges are pairs of vertices, with no ordering-unlike our formalization
   with relations as sets of ordered pairs. So, here treat the edges as ordered pairs as
   follows: For any graph G = (V, E), let k be the set of all ordered pairs (vi, v2) and
   (v2, VI) where (V1, v2) e E. Show that CONN is the reflexive and transitive closure
   of E.


3. Find a graph G such that G is not connected.


4. Let G be a graph. Prove that if G is disconnected, then G is connected.


5. Let G = (V, E) be a connected graph with at least two vertices. Prove that if I V I >
   I E 1, then G has a vertex of degree one.


6. Suppose that 2n computers are networked so that each computer is connected to n
   other computers. Prove that it is always possible for any pair of computers to pass
   messages to one another. (Hint: See Exercise 40 in Section 6.6.)


7. Let G be a connected graph with average degree greater than two. Prove that G con-
   tains at least two cycles.
   For problems involving depth first and breadth first searches, assume the adjacency
   lists are formed by listing the adjacencies of each vertex in increasing order.


8. Carry out a depth first search on the graph in Figure 6.22 starting at the vertex f.
   Display the result of the search process as was done in Figure 6.22.


9. Carry out a depth first search on the graph in Figure 6.22 starting at the vertex e.
   Display the result of the search process as was done in Figure 6.22.


10. Carry out a breadth first search on the graph in Figure 6.24 starting at the vertex f.
    Display the result of the search process as was done in Figure 6.24.


11. Carry out a breadth first search on the graph in Figure 6.24 starting at the vertex g.
    Display the result of the search process as was done in Figure 6.24.


12. Let the graph G be given by the following adjacency list:

Vertices List of Adjacencies

1 2 6 7 8

2 1 3 4

3 2 4 5 6

4 2 3

5 3

6 1 3

7 1 8 9 10

8 1 7 9 10

9 7 8

10 7 8