Question 2.103

73.

  1. Show that for each edge of graph J, which follows, there is a spanning tree of J that avoids that edge.
  2. For each spanning tree that you found in graph J, count the number of vertices and edges. Do you notice any pattern?
  3. For graph H, which follows, and each edge in the graph, is there a spanning tree that does not include that edge of H?
image

73.

(a) Answers will vary for each edge.

(b) 5; one less than the number of vertices in the graph

(c) No (CD and AG must be included in any spanning tree.)

image