Solutions

  1. Answer: In Figure 9.1.10, computer b can communicate with all other computers. In Figure 9.1.11, there are direct roads to and from city b to all other cities.

  2. Answer:


  3. Answer: The maximum number of edges would be \binom{8}{2} = \frac{(7)(8)}{2} = 28.

  4. Answer:
    1. \binom{n}{2} = \frac{(n-1)n}{2}
    2. n - 1, each vertex except the champion vertex has an indegree of 1 and the champion vertex has an indegree of zero.

  5. Answer:
    1. Not graphic - if the degree of a graph with seven vertices is 6, it is connected to all other vertices and so there cannot be a vertex with degree zero.
    2. Graphic. One graph with this degree sequence is a cycle of length 6.
    3. Not Graphic. The number of vertices with odd degree is odd, which is impossible.
    4. Graphic. A "wheel graph" with one vertex connected to all other and the others connected to one another in a cycle has this degree sequence.
    5. Graphic. Pairs of vertices connected only to one another.
    6. Not Graphic. With two vertices having maximal degree, 5, every vertex would need to have a degree of 2 or more, so the 1 in this sequence makes it non-graphic.