Question

Let n ≥ 5 be an odd integer. Use induction method to prove that there is no 3-regular graph with n vertices.

Answer 1

Answer:

Given That,

Graph has odd number of vertices where vertices are greater than or equal to 5

And the graph should be 3-regular which means every vertex in the graph should have a degree 3 .

which means the number of vertices having degree 3 should be odd as the graph odd number of

vertices but from the above given theorem it is impossible because the number of vertices with degree

3 should be even but graph always has odd number of vertices.

Explanation: