I'm reading Arthur Engel's "Problem Solving Strategies". On problem E8 he gives this theorem:
Let $G$ be a linear graph of $n$ vertices. Then $G$ has a Hamiltonian path if the sum of the degrees of any two vertices is equal to or larger than $n-1$.
I'm confused on what he means. I googled "linear graph" and most of the results were about plotting 2-D functions. This Wikipedia article defines a linear graph as
A path graph or linear graph is a graph whose vertices can be listed in the order $v_1, v_2, …, v_n$ such that the edges are $\{v_i, v_{i+1}\}$ where $i = 1, 2, …, n − 1$.
By that definition, wouldn't every linear graph have a Hamiltonian path? Am I understanding the theorem wrong or do I have a wrong definition?
The theorem seems to be related to Ore's Theorem, which I found from this website:
If $G$ is a simple graph with $n$ vertices, $n≥3$, such that $deg(u)+deg(v)≥n$ for every pair of non-adjacent vertices $u$ and $v$ in $G$, then $G$ has an Hamilton’s circuit.
From Ore's, I've been thinking that "linear graph" just means a simple graph, but I'd like to make sure. Thanks for the help.
Yes, a linear graph does seem to be just a simple graph. If you are looking for more information the following website included diagrams to clarify its theories: http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%203.PDF It also discusses the Hamilton path amongst other processes.