Question

Find a spanning tree for each of these graphs.

a) \({{\bf{K}}_5}\) b) \({{\bf{K}}_{{\bf{4,4}}}}\)c) \({{\bf{K}}_{{\bf{1,6}}}}\)

d)\({{\bf{Q}}_{\bf{3}}}\)e) \({{\bf{C}}_{\bf{5}}}\)f )\({{\bf{W}}_{\bf{5}}}\)

Short answer

For the result follow the steps.

Step-by-step solution

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and that does not contains any single circuit. And a tree with n vertices has n-1 edges.

(a)Step 2: Spanning tree for \({{\bf{K}}_{\bf{5}}}\).

The graph with 5 vertices and an edge between every pair of vertices.

The spanning tree will then contain 5 vertices and 4 edges.

The easiest way to create the spanning three is by creating a path that pass that through all vertices exactly once. The spanning tree can be draw by removing one edge.

(b)Step 3: Sketch spanning tree for \({{\bf{K}}_{{\bf{4,4}}}}\).

This is a graph of 4 vertices M=(a,b,c,d) and another set of 4 vertices N=(e,f,g,h).All vertices in M are connected to vertex in N.

The spanning tree will then contain 8 vertices and 7 edges.

The easiest way to create the spanning three is by creating a path that pass that through all vertices exactly once.

(c)Step 4: Plot spanning tree \({{\bf{K}}_{{\bf{1,6}}}}\).

This is a graph of 1 vertices M=(a) and another set of 6 vertices N=(b,c,d,e,f,g).All vertices in M are connected to vertex in N.

The spanning tree will then contain 7 vertices and 6 edges.

However this graph contains 6 edges and is also a tree, thus the spanning tree is itself.

(d)Step 5: Draw spanning tree of \({{\bf{Q}}_{\bf{3}}}\).

The graph with 8 vertices.

Tha spanning tree will contain 8 vertices and 7 edges.

The easiest way to create the spanning three is by creating a path that pass that through all vertices exactly once.

(e)Step 6: Plot spanning tree for \({{\bf{C}}_{\bf{5}}}\).

The graph with 5 vertices and an edge between every pair of vertices.

The spanning tree will then contain 5 vertices and 4 edges.

The easiest way to create the spanning three is by creating a path that pass that through all vertices exactly once. The spanning tree can be draw by removing one edge.

(f)Step 7: Sketch spanning tree for \({{\bf{W}}_{\bf{5}}}\). 

The spanning tree will then contain 6 vertices and 5 edges.

The easiest way to create the spanning three is by creating a path that pass that through all vertices exactly once. The spanning tree can be draw by removing one edge.

This is the required result.