Since we know 2 vertices $w_i \in W \text{ and } u_j \in U$ are adjacent if $1 \leq i, u \leq n$, this makes every vertex in W adjacent to every vertex in U giving us a bipartite graph.
The correct statement here would be:
- Since every edge is between a vertex in $W$ and a vertex in $U$, we have a bipartite graph. (The line I quoted from your proof doesn't say anything about edges in $W \times W$ or $U \times U$. Their non-existence is the crucial point).
- Since the edge set is the full Cartesian product $W \times U$, we have a complete bipartite graph.
So the task at hand condenses down to finding the number of
hamiltonian cycles in a complete bipartite graph with n and n vertices
i.e. $K_{n,n}$.
Correct.
Which is $\frac{n!(n-1)!}{2}$, taken from here.
Yes, but the main point of the exercise is probably to show why that's the correct result.
No, there is no such example.
It is easier to ask: is there an $n$-vertex graph $G$ such that $\deg(u)+\deg(v) = n-1$ for one non-adjacent pair $u,v$, and $\deg(u)+\deg(v) \ge n$ for all other non-adjacent pairs, which does not have a Hamiltonian cycle? If the graph in your question exists, then by the adding-$w$ trick, this one must as well.
Suppose such a $G$ exists. Then $G+uv$ satisfies the hypotheses of Ore's theorem and has a Hamiltonian cycle. Either that cycle exists in $G$, or else $G$ at least has a $u-v$ Hamiltonian path: a path $(x_1, x_2, \dots, x_n)$ with $x_1 = u$ and $x_n = v$.
Suppose that $\deg(u) \ge 2$ (if not, look at $v$ instead of $u$), and let $x_i$ with $i>2$ be any neighbor of $u = x_1$. Then there is also a Hamiltonian path $(x_{i-1}, x_{i-2}, \dots, x_1, x_i, x_{i+1}, \dots, x_n)$ - and in this Hamiltonian path, $\deg(x_{i-1}) + \deg(x_n) \ge n$.
Now we can follow the standard proof of Ore's theorem to show that this Hamiltonian path can be turned into a Hamiltonian cycle. We conclude that $G$ is Hamiltonian; a single pair with $\deg(u)+\deg(v)=n-1$ is not enough to break the theorem.
In fact, a stronger argument can be made. Suppose that $G$ has fewer than $n-2$ non-adjacent pairs $u,v$ with $\deg(u)+\deg(v)=n-1$; for all other non-adjacent pairs $u,v$ the degree sum is $\deg(u)+\deg(v) \ge n$.
Then $G$ has a Hamiltonian path $(x_1, x_2, \dots, x_n)$ and by the argument above, we can turn this path into a total of $\deg(x_1) \cdot \deg(x_n)$ different Hamiltonian paths. Since $x_1, x_n$ cannot be adjacent, $\deg(x_1) + \deg(x_n) \ge n-1$, so $\deg(x_1) \cdot \deg(x_n) \ge n-2$. Therefore at least one of the Hamiltonian paths we get must end at vertices whose degree sum is at least $n$, and then the argument of Ore's theorem turns it into a Hamiltonian cycle.
The bound $n-2$ is tight: otherwise, take a $K_{n-1}$, and add a leaf vertex adjacent to one of its vertices. Here, there is no Hamiltonian cycle, and only $n-2$ pairs of non-adjacent vertices, each with degree sum $n-1$.
Similarly, for the Hamiltonian path question, we can take a $K_{n-1}$ together with an isolated vertex. Here, there is no Hamiltonian path, and only $n-1$ pairs of non-adjacent vertices, each with degree sum $n-2$. This is best possible.
Best Answer
First, the negation of $P$ is not "$\deg(v) + \deg(w) < n$ for every pair of distinct, non-adjacent $v,w$" but "there exists a pair of distinct, non-adjacent $v,w$ for which $\deg(v) + \deg(w) < n$". So that's all that being non-Hamiltonian implies.
In general, the negation of a property that says "all things behave in a certain way" is "at least one thing behaves differently", not "all things behave differently".
Second, Ore's theorem can never help us work out if a graph is not Hamiltonian. It gives us a condition that, if true, tells us that $G$ is Hamiltonian. If $P$ is false, we do not learn anything.