This chapter showcase some of the illustrations of Graph Theory concepts.
From the following graph, identify the number of spanning trees.
There are 3 spanning trees obtained from the above graph. The spanning trees are depicted below:
It is observed that graph I and graph II are isomorphic and hence there is one non-isomorphic spanning tres.
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:
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.
For a complete graph Kn, what is the chromatic number?
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.
What is the matching number for the following graph?
Number of vertices = 9
Only 8 vertices can be matched and hence
Matching number is 4.
For the graph given below, identify the line covering number.
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.
Graph Theory Tutorial
All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.