Graph Theory Examples - Graph Theory

Demonstrate few examples on the concepts of Graph Theory

This chapter showcase some of the illustrations of Graph Theory concepts.

Example 1

From the following graph, identify the number of spanning trees.

Spanning Tree Example


There are 3 spanning trees obtained from the above graph. The spanning trees are depicted below:

Obtained Spanning Trees

It is observed that graph I and graph II are isomorphic and hence there is one non-isomorphic spanning tres.

Example 2

By suing 3 vertices, how many non-isomorphic graphs can be obtained?


By using 3 vertices, four non-isomorphic graphs can be drawn, which are depicted below:

Non - isomorphic Example

Example 3

Fine the number of regions of the graph G which has 20 vertices and which is a connected planar and which has 3 as each vertex degree.


By the sum of degrees theorem,

20(3) = 2|E|

|E| = 30

By Euler’s formula,

|V| + |R| = |E| + 2

20+ |R| = 30 + 2

|R| = 12

Therefore, the number of regions is 12.

Example 4

For a complete graph Kn, what is the chromatic number?


Chromatic Number Example

As each of the vertex is adjacent to others, a new colour is required by each of the vertices and hence the chromatic number Kn = n.

Example 5

What is the matching number for the following graph?


Matching Number Example

Number of vertices = 9

Only 8 vertices can be matched and hence

Matching number is 4.

Matching Number Example

Example 6

For the graph given below, identify the line covering number.


Line Covering Number Example

Number of vertices = |V| = n = 7

Line covering number =

α1 ≥ 3

All the vertices can be covered by using three edges and

Therefore, the line covering number is 3.

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd Protection Status

Graph Theory Topics