Welcome to our community

Be a part of something great, join today!

Hamiltonian circuits

Joystar1977

Active member
Jul 24, 2013
119
Consider the complete graph with 5 vertices, denoted by K5.

E.) Does K5 contain Hamiltonian circuits? If yes, draw them.

I know that a Hamiltonian circuit is a graph cycle through a graph that visits each node exactly once. However, the trivial graph on a single node is considered to possess a Hamiltonian cycle, but the connected graph on two nodes is not. A graph possessing a Hamiltonian circuit is said to be a Hamiltonian graph.

Is it correct that K5 doesn't contain Hamiltonian circuits because this is a connected graph on two nodes?
 

Tranquillity

Member
Feb 22, 2012
36

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193
It does not have two nodes, but five nodes. Any complete graph with more than two vertices has a Hamiltonian cycle: just go around the graph in order.
 

Joystar1977

Active member
Jul 24, 2013
119
Consider the complete graph with 5 vertices, denoted by K5.

Does K5 contain Hamiltonian circuits? If yes, draw them.

Is it correct to say that K5 does contain Hamiltonian circuits because it has more than two vertices?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193
Is it correct to say that K5 does contain Hamiltonian circuits because it has more than two vertices?
Well, having more than two vertices is not sufficient, by itself, to ensure that any particular graph contains a Hamiltonian circuit. It is necessary. However, because $K_{5}$, in addition to having more than two vertices, contains an edge from any vertex to any other vertex, it is quite straight-forward to construct a Hamiltonian circuit.