11.1 (513-518)
3. For the graph in Fig. 11.7, how many paths are there from b to f ?
There are 6 paths from b to f:
(b, a, c, d, e, f), (b, c, d, e, f), (b, e, f), (b, a, c, d, e, g, f), (b, c, d, e, g, f), and (b, e, g, f)
11. Let G be a graph that satisfies the condition in Exercise 10.
a) Must G be loop-free?
b) Could G be a multigraph?
c) If G has n vertices, can we determine how many edges it has?
a) Yes, G must be loop-free because an edge is a bridge only if that edge is not contained in any cycles. A loop is a cycle.
b) Yes, G can be a multi-graph. For example, the multi-graph in Figure 11.6 (pg. 518) becomes disconnected if we remove edge (c, e). This would leave two components of (a, b, c) and (d, e).
c) Yes, G would have n – 1 edges for n vertices; the same vertex closes a graph and there is always a vertex at the start and end, which means there is one more vertex than an edge.
11.2 (520-528)
4. If G = (V, E) is an undirected graph, how many spanning subgraphs of G are also induced subgraphs?
The undirected graph G = (V, E) has 2|E| spanning subgraphs, one for each subset of the edge set, and 2|V| induced subgraphs, one for each subset of the vertex set.
11.3 (530-537)
5. Let G1 = (V1, E1) and G2 = (V2, E2) be the loop-free undirected connected graphs in Fig. 11.42.
a) Determine |V1|, |E1|, |V2|, and |E2|.
Counting the vertices and edges in both graphs:
|V1| = |V2| = 8
|E1| = |E2| = 14
11.4 (540-553)
3a. How many vertices and how many edges are there in the complete bipartite graphs K4,7, K7,11, and Km,n, where m, n, ∈ Z+?
K4,7 = 11 vertices (4 + 7) = 28 edges (4 * 7)
K 7,11 = 18 vertices (7 + 11) = 77 edges (7 * 11)
Km,n = m + n vertices = m * n edges
11.5 (556-562)
2. Characterize the type of graph in which an Euler trail (circuit) is also a Hamilton path (cycle).
A Euler trail is open and crosses each edge at least once without repeating. A Hamilton path passes
