Question

urgent
Anyone please answer

Prove that there can be no path longer than a hamiltonian path (if it exists) in a graph?​

Answer 1

Answer:

A Hamiltonian path in a graph is a path involving all the vertices of the graph. In this paper, we revisit the famous Hamiltonian path problem and present new sufficient conditions for the existence of a Hamiltonian path in a graph.

1. Introduction

Hamiltonian paths and cycles are named after William Rowan Hamilton who invented the puzzle that involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Although Hamilton solved this particular puzzle, finding Hamiltonian cycles or paths in arbitrary graphs is proved to be among the hardest problems of computer science [1]. As a result, instead of complete characterization, most researchers aimed to find sufficient conditions for a graph to possess a Hamiltonian cycle or path. In this paper, we focus on degree based sufficient conditions for the existence of Hamiltonian paths in a graph.

To the best of our knowledge, the quest for good sufficient degree based conditions for Hamiltonian cycles or paths dates back to 1952 when Dirac presented the following theorem, where denotes the degree of the minimum degree vertex of the graph .

Theorem 1 (see [2]). If is a simple graph with vertices, where and , then contains a Hamiltonian cycle.

Later Ore in 1960 presented a highly celebrated result where a lower bound for the degree sum of nonadjacent pairs of vertices was used to force the existence of a Hamiltonian cycle. In particular, Ore proved the following theorem, where denotes the degree of the vertex .

Theorem 2 (see [3]). Let be a simple graph with vertices and , distinct nonadjacent vertices of with . Then, has a Hamiltonian cycle.