0
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ How do you define a countable Hamiltonian path? $\endgroup$ – Pablo Feb 20 '15 at 11:17
  • 3
    $\begingroup$ In your conjecture, why do you need two vertices if you take $\max$ anyway? $\endgroup$ – Alex Degtyarev Feb 20 '15 at 11:25
2
$\begingroup$

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$).

$\endgroup$
  • 1
    $\begingroup$ Do you mean the countably infinitely branching tree? A star would definitely contain non-adjacent pairs with finite total degree. $\endgroup$ – Ben Barber Feb 20 '15 at 11:47
  • $\begingroup$ @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. $\endgroup$ – Alex Degtyarev Feb 20 '15 at 11:54
  • 4
    $\begingroup$ 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. $\endgroup$ – bof Feb 20 '15 at 12:32
  • 3
    $\begingroup$ 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. $\endgroup$ – bof Feb 20 '15 at 12:52
  • 1
    $\begingroup$ @bof Of course, sorry. I just didn't know the original theorem, and I'm used to reading "a" as $\exists$ rather than $\forall$ :) $\endgroup$ – Alex Degtyarev Feb 20 '15 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.