Question

is the graph in figure 2 a spanning tree for the connected graph given in figure 1?

yes, because figure 2 is a subgraph of figure 1.
yes, because the subgraph contains all of the original graphs vertices, it is connected, and it contains no circuits. it also has one less edge than it has vertices.
no, because the subgraph contains all of the original graphs vertices, it is connected, and it contains no circuits. it also has one less edge than it has vertices.
no, because figure 2 is not a subgraph of figure 1.

Explanation:

Identify the vertices and edges of Figure 1

Figure 1 is a connected graph with 5 vertices:

$$ V_1 = \{A, B, C, D, E\} $$

The edges present in Figure 1 are:

$$ E_1 = \{AB, BD, DE, EC, CA\} $$

Identify the vertices and edges of Figure 2

Figure 2 has the same 5 vertices:

$$ V_2 = \{A, B, C, D, E\} $$

The edges present in Figure 2 are:

$$ E_2 = \{AB, EC, CA, ED\} $$

Notice that the edge \(BD\) from Figure 1 is missing in Figure 2.

Check the definition of a spanning tree

A spanning tree of a connected graph must satisfy:

1. It is a subgraph of the original graph.
2. It contains all vertices of the original graph (it spans).
3. It is connected.
4. It contains no circuits (it is a tree).

Evaluate Figure 2 against the criteria

Let's test if Figure 2 is connected:

• Vertex \(B\) is only connected to vertex \(A\) via edge \(AB\).
• Vertices \(A, C, E, D\) form a connected path: \(A - C - E - D\).
• Since \(B\) is connected to \(A\), all vertices \(\{A, B, C, D, E\}\) are connected to each other.
• Thus, Figure 2 is connected.

Let's check for circuits:

• There are no closed loops (circuits) in Figure 2.

Let's check the vertex and edge count:

• Number of vertices \(n = 5\).
• Number of edges \(e = 4\).
• A tree with \(n\) vertices must have exactly \(n - 1\) edges. Here, \(4 = 5 - 1\), which is correct.

Match with the given options

Since Figure 2 is a subgraph containing all vertices, is connected, has no circuits, and has one less edge than vertices, it is indeed a spanning tree.
This matches the second option: "Yes, because the subgraph contains all of the original graph's vertices, it is connected, and it contains no circuits. It also has one less edge than it has vertices."

Answer:

• Yes, because Figure 2 is a subgraph of Figure 1.
• Yes, because the subgraph contains all of the original graph's vertices, it is connected, and it contains no circuits. It also has one less edge than it has vertices. (Correct answer)
• No, because the subgraph contains all of the original graph's vertices, it is connected, and it contains no circuits. It also has one less edge than it has vertices.
• No, because Figure 2 is not a subgraph of Figure 1.