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

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

1 Answer 1

Reset to default
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$).

Improve this answer
$\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
    Commented 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$
    – Alex Degtyarev
    Commented 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
    Commented 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
    Commented 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$
    – Alex Degtyarev
    Commented Feb 20, 2015 at 12:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .