Question

Use depth-first search to find a spanning tree of each ofthese graphs.

a)\({W_{\bf{6}}}\)(See Example 7 of Section 10.2), starting at the vertex of degree 6.

b)\({{\bf{K}}_{\bf{5}}}\)

c)\({{\bf{K}}_{{\bf{3,4}}}}\), starting at a vertex of degree 3

d) \({{\bf{Q}}_{\bf{3}}}\)

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.

Use depth-first search.

Starts from any random chosen root and then create a path by successively adding vertices to the path that we adjacent to the previous vertex in the path and the vertex that is added cannot be in the path.

Solution for \({{\bf{W}}_{\bf{6}}}\).

Here \({{\bf{W}}_{\bf{6}}}\)is a cycle \({{\bf{C}}_{\bf{6}}}\)with an additional vertex that is connected to all other vertices.

Let the 7 vertices are a,b,c,d,e,f,g with a the vertex connected to all other vertices.

Starts form vertex a. So, path =a.

And a is adjacent to the b,c,d,e,f,g. Since b occurs first so we add b first then path=a,b.

Now b is connected to c,g.Since c comes first then path=a,b,c.

The next path c is connected to d. Then path=a, b,c,d.

Apply the same procedure. And the path is

Path=a,b,c,d,e,f,g

The spanning tree then needs to contains all edges contained in the path a, b,c,,d,e,f,g.

The spanning tree is

Step 4:Result for \({{\bf{K}}_{\bf{5}}}\).

Here \({{\bf{K}}_{\bf{5}}}\)has 5 vertices and edges between every pair of vertices.

Let the 5 vertices are a,b,c,d,e with a the vertex connected to all other vertices.

Starts form vertex a.So path=a.

And a is adjacent to the b,c,d,e. Since b occurs first so we add b first then path=a,b.

Now b is connected to c,d,e.Since c comes first then path=a,b,c.

The next path c is connected to d,e. Then path=a, b,c,d.

Apply the same procedure . And the path is

Path=a,b,c,d,e.

The spanning tree then needs to contains all edges contained in the path a, b,c,,d,e.

The spanning tree is

Find the result of \({{\bf{K}}_{{\bf{3,4}}}}\).

Here \({{\bf{K}}_{{\bf{3,4}}}}\)contains set of 3 vertices M=a,b,c and a set of 4 vertices N=d,e,f,g.

Every vertex in M is connected to vertex in N.

Starts form vertex d.So path=d.

And d is adjacent to the a,c,d. Since b occurs first so we add b first then path=d,a.

Now a is connected to e,f,g.Since e comes first then path=d,a,e.

The next path e is connected to b,c. Then path=d,a,e,b.

Apply the same procedure. And the path is

Path=d,a,e,b,f,c,g.

The spanning tree then needs to contains all edges contained in the path d,a,e,f,c,g.

The spanning tree is

Find the spanning tree for \({{\bf{Q}}_{\bf{3}}}\).

Here \({{\bf{Q}}_{\bf{3}}}\)contains the bit strings of 3 vertices 000,001,011,100,101,110,111.

Vertices are connected if exactly one of the bits of the strings differ.

Starts form vertex 000.So path=000.

And 000 is adjacent to the 001,010,100. Since 001 occurs first so we add b first then path=000,001.

Now 001 is connected to 011,101.Since 011 comes first then path=000,001,011.

The next path 011 is connected to 010,111. Then path=000,001,011,010.

Apply the same procedure. And the path is

Path=000,001,011,010,110,100,101,111.

The spanning tree then needs to contain all edges contained in the path 000,001,011,010,110,100,101,111.

The spanning tree is

This is the required result.