in this chapter, we will cover a few standard examples to demonstrate the concepts we already discussed in the earlier chapters.

example 1

find the number of spanning trees in the following graph.

solution

the number of spanning trees obtained from the above graph is 3. they are as follows −

these three are the spanning trees for the given graphs. here the graphs i and ii are isomorphic to each other. clearly, the number of non-isomorphic spanning trees is two.

example 2

how many simple non-isomorphic graphs are possible with 3 vertices?

solution

there are 4 non-isomorphic graphs possible with 3 vertices. they are shown below.

example 3

let ‘g’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. find the number of regions in the graph.

solution

by the sum of degrees theorem,

20 σ i=1 deg(vi) = 2|e|

20(3) = 2|e|

|e| = 30

by euler’s formula,

|v| + |r| = |e| + 2

20+ |r| = 30 + 2

|r| = 12

hence, the number of regions is 12.

example 4

what is the chromatic number of complete graph k_n?

solution

in a complete graph, each vertex is adjacent to is remaining (n–1) vertices. hence, each vertex requires a new color. hence the chromatic number k_n = n.

example 5

what is the matching number for the following graph?

solution

number of vertices = 9

we can match only 8 vertices.

matching number is 4.

example 6

what is the line covering number of for the following graph?

solution

number of vertices = |v| = n = 7

line covering number = (α₁) ≥ [n/2] = 3

α₁ ≥ 3

by using 3 edges, we can cover all the vertices.

hence, the line covering number is 3.