Question

# a graph is regular of degree k if every vertex has the same degree, k. show...

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.

#### Homework Answers

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

Know the answer?
Your Answer:

#### Post as a guest

Your Name:

What's your source?

#### Earn Coins

Coins can be redeemed for fabulous gifts.

##### Not the answer you're looking for?
Ask your own homework help question
ADVERTISEMENT
##### Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

ADVERTISEMENT