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$
2
  • $\begingroup$ How do you define a countable Hamiltonian path? $\endgroup$
    – Pablo
    Feb 20, 2015 at 11:17
  • 3
    $\begingroup$ In your conjecture, why do you need two vertices if you take $\max$ anyway? $\endgroup$ Feb 20, 2015 at 11:25

1 Answer 1

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$
6
  • 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, 2015 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$ Feb 20, 2015 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, 2015 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, 2015 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$ Feb 20, 2015 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.