Answer to Question #242427 in Discrete Mathematics for yassal

Question

Can a simple graph exist with 15 vertices each of degree five?

Answer 1

In Graph Theory, Handshaking Theorem states in any given graph, Sum of degree of all the vertices is twice the number of edges contained in it.

Let $G = (V, E)$ be an undirected graph with $m$ edges. Then

$$2m=\displaystyle\sum_{\nu\in V}\deg(\nu)$$

The sum of the degrees of the vertices $5 ⋅ 15 = 75$  is odd. 

Therefore by Handshaking Theorem a simple graph with 15 vertices each of degree five cannot exist.