Question

How many edges must be removed from the wheel graph W6 in order to create a spanning tree for the graph?

a) 5
b) 6
c) 7
d) The graph does not have a spanning tree.

Answer 1

Answer:

The correct option is A.

Step-by-step explanation:

If a graph is formed by connecting a single universal vertex to all vertices of a cycle, then it is known as wheel graph.

W₆ means wheel graph having 6 vertices as shown in the below figure.

Total number of edges in a wheel graph is 2(n-1), where n is number of vertices. So, the number of edges in W₆ is

$2(6-1)=10$

In a spanning tree all the vertices covered with minimum possible number of edges. Total number of edges in a spanning tree is (n-1).

Total number of edges in a spanning tree which has 6 vertices is

$6-1=5$

The number of edges we need to remove is

$10-5=5$

Therefore the correct option is A.