#GRAPH THEORY

Question

A simple regular graph n vertices and 24 edges, find all possible values of n.

Comments

Possible values of n are: 8,12,16,24,48

Answer 1

Regular graph. So all the vertices must have the same degree.

Let there be n vertices.

We know that , $\sum deg(V_{i}) = 2*E , where \ V_{i} \ is \ vetex$.

Let $x$ be the degree of each vertex.

Thus , $nx = 48 => n = \frac{48}{x} $

when $x = 1$. There will be 48 vertices , each of degree 1. Possible.

when $x =2$. There will be 24 vertices , each of degree 2 . Also possible.

when $x = 3$ . 16 vertices of degree 3 . A simple graph is possible . Can be proved with Havell Hakimi's result.

when $x = 4$ . 12 vertices of degree 4. Possible.

when $x = 6$. 8 vertices of degree 6 each. Possible.

Beyong this , for example , 6 vertices of degree 8 is not possible as a simple graph . Because maximum degree a 6 vertex simple graph can have is 5.

So answer will be <8,12,16,24,48>

Answer 2

Since the degree of each vertex will be same let it be K ( graph is regular ).

We know sum of all degrees is equal to 2e

So nk =2*24

nk =48

Also remember maximum degree in n vertex graph can be n-1 .

Now substitute values satisfying above relation and find values of n