Question

a graph is regular of degree k if every vertex has the same degree, k. show that G has a hamiltonian circuit if G has 13 vertices and is regular of degree 6.

Answer 1

Given

G is regular graph with vertices n=13

Order =6 and by definition of regular graph

Degree of each vertex=6

Now by theorems stated below:

Dirac Theorem- “If G is a simple graph with n vertices with n>=3 such that the degree of every vertex in G is at least n/2, then G has a Hamiltonian circuit.”

Ore’s Theorem- “If G is a simple graph with n vertices with n>=3 such that deg(u) + deg(v)>=n for every pair of non-adjacent vertices u and v in G, then G has a Hamiltonian circuit.”

Since 6<13/2

Also 6+6<13

So this doesn't satisfy both Dirac and ore's theorem.

Therefore G doesn't have a Hamiltonian circuit.

Hope you get your answer. Thank you and please like the answer