# Ore's theorem for countable graphs

Ore's theorem states that in a finite graph $G$ with $|V(G)|=n$, there is a Hamiltonian path, provided that the sums of the degrees of 2 distinct, non-adjacent vertices is $\geq n$.

For countable graphs, such a statement cannot hold: consider the disjoint union of two copies of $K_\omega$.

How about if we restrict ourselves to connected countable graphs? Is then the following statement true?

If $G$ is a connected countable graph such that for distinct, non-adjacent vertices $v,w$ we have $\text{max}\{\text{deg}(v), \text{deg}(w)\} = \aleph_0$, there is an countable Hamiltonian path (extending in two ways, or beginning at one vertex.)

• How do you define a countable Hamiltonian path? Feb 20, 2015 at 11:17
• In your conjecture, why do you need two vertices if you take $\max$ anyway? Feb 20, 2015 at 11:25

And then here is an obvious counterexample: take a star-like tree with one central vertex of countable degree (and, if you still insist on two non-adjacent vertices, make each ray of length $2$).
• @BenBarber Yes, but Dominic wants a pair of non-adjacent vertices with one of these vertices of infinite degree. In fact, one can also have two vertices, both infinite, by splicing a pair of such trees. Anyway, the thing with Ore's theorem is that a certain set almost covers the whole graph; this follows from simple counting in the finite case, but it does not follow in the numbers are infinite (you know, $\infty-\infty$ can be anything :). Probably, the right conjecture would be to consider some kind of codegrees or such. Feb 20, 2015 at 11:54
• Ore's theorm for finite graphs assumes that every pair of distinct nonadjacent vertices has degree-sum at least $n$. I suppose that this question about infinite graphs also has an implicit universal quantifier. But the OP accepted your answer, so I must be wrong.
• Of course the answer is negative, but one should give a correct counterexample. Yes, the infinitely branching tree (with degree $\aleph_0$ at each node) is much better.
• @bof Of course, sorry. I just didn't know the original theorem, and I'm used to reading "a" as $\exists$ rather than $\forall$ :) Feb 20, 2015 at 12:55