# 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. ### Solution

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.

### Example 2

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

### Solution

By using 3 vertices, four non-isomorphic graphs can be drawn, which are depicted below: ### 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.

### Solution

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?

### Solution 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?

### Solution Number of vertices = 9

Only 8 vertices can be matched and hence

Matching number is 4. ### Example 6

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

Solution 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 Related Practice Tests

Graph Theory Topics