Find a spanning tree for the connected graph.
Solution:-
Given a graph, a sub graph is a set vertices and edges chosen from those of the original graph. A graph can have many subgraphs. A subgraph that contains all of a connected graph’s vertices, is connected, and contain no circuits is called a spanning tree. A graph can have many spanning trees.
The original graph is a connected graph with 6 vertices and 8 edges.
The spanning tree of a graph with n vertices has n – 1 edges.
Therefore , the spanning tree of the original graph must have 6 – 1 = 5 edges. Since the original graph has 8 edges, 3 edges will need to be removed to create the spanning tree.
Remove three edges to create one possible spanning tree, as shown to the right. Notice that each edge is a bridge and no circuits are present.
