Why is the complete graph $K_2$ not Hamiltonian?

1.5k Views Asked by At

Why is the complete graph $K_2$ not Hamiltonian?

A graph $G$ is said to be Hamiltonian if there exists a path in $G$ which visits every vertex exactly once. Also a path is a sequence of vertices and edges.

I am stuck on this.I see everywhere it is not Hamiltonian. But why? Cant we take $v_1e_1v_2e_1v_1$ as a closed path from $v_1$ to $v_2$.

Also here every vertex is visited only once, only the edge $e_1$ is repeated which is allowed.

So why is it not Hamiltonian? Can someone kindly help.

2

There are 2 best solutions below

3
On

You seem to want a Hamiltonian cycle. Details of paths, cycles, trails, walks, et c. depend on one's definitions.

Hamiltonian path : "A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle."

Cycle: "a cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices."

Trail: "A trail is a walk in which all edges are distinct."

So, no, a Hamiltonian cycle is not permitted to reuse an edge.

3
On

A Hamiltonian graph must have a special cycle, and all cycles are circuits, and all circuits are trails, and all trails cannot visit an edge more than once.