What is a max non hamiltonian graph?

Question

Assume we're taking about simple graphs here.

What is the exact definition of a non-hamiltonian graph ?

Is it true if I say that:

Adding one single edge to the max non-hamiltonian graph, will make it hamiltonian ?

Answer 1

Let's start with Wikipedia's definition of a hamiltonian path.

A Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once.

Thus a non-Hamiltonian graph is one where a Hamiltonian path does not exist. A max non-Hamiltonian graph is the largest graph that is non-Hamiltonian. Suppose you could add a single edge to stay non-Hamiltonian. This would mean your initial graph was not a max non-Hamiltonian graph. Thus, adding one single edge to the max non-Hamiltonian graph will make it Hamiltonian.

Answer 2

For the second yes, by adding a new edge to a max non-Hamiltonian graph you make it Hamiltonian. A Hamiltonian graph is a graph which has a Hamiltonian path. See the definition of Hamiltonian path in Wikipedia.