Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to understand the basics of Infinite Graph theory and various preconditions in Konig's Lemma. The texts I have studied tend to use the Axiom of Choice (usually Zorn's Lemma) as a tool of mathematics rather than an assumption about Graphs. In doing so a potential class of graphs - introduced below - does not get discussed: so why is this?

To be specific, consider the following Infinite Graph theory definition and theorems (from Wilson's Introduction to Graph Theory):

$Definition:$ An infinite graph is $locally-countable$ if every vertex has countable degree.

$Theorem:$ Every connected locally-countable infinite graph is countable.

$Corollary:$ Every connected locally-finite infinite graph is countable.

The Theorem above (and hence the corollary) is proven using:

The union of a countable collection of countable sets is countable.

As this latter is a corollary of AC (and weaker versions) it is not valid in ZF, only ZFC. In summary this form of Infinite Graph theory is really a "ZFC-Graph Theory". In a hypothetical "ZF-Graph Theory" the above Theorem as stated is false and needs to be restated with the relevant preconditions.

Of course it is not just the above Theorem which is false, but Konig's (1936) Lemma itself, as usually stated. For example this statement from Wikipedia:

If G is a connected graph with infinitely many vertices such that every vertex has finite degree (that is, each vertex is adjacent to only finitely many other vertices) then G contains an infinitely long simple path, that is, a path with no repeated vertices.

Now to make more explicit the point about "missing graphs" I shall summarise another variant of Konig's Lemma and then demonstrate what seems to be missing:

$Theorem:$ Let G be an infinite connected locally countable graph. Then G contains either (i) a node of countable degree; (ii) an infinite path

In ZF-Graph Theory it would say: Then we have at least 3 cases: (i) G is countable and contains a node of countable degree; (ii) G is countable and has an infinite path; (iii) G is not countable but is the countable union of countable sub-graphs.

Additional Question: Are there any other cases for the type of graph specified?

Although at first this ZF form seems clumsy, by combining the geometric interpretation of "local" with this result we have the following fact in the ZF-Infinite Graph theory not valid in the usual ZFC-Infinite Graph theory of the textbooks:

There exists infinite graphs which are locally-countable but not globally countable.

So are there "missing graphs" of this type in Infinite Graph theory - and if so why?

Comment: The Comments below seem to suggest that Graph Theorists are deliberately avoiding "ZF-Graph theory" because it would be complex, wooly and unstructured. This might be true, but it still suggests the existence of a wider class of Infinite Graphs.

share|cite|improve this question
You don't necessarily have your last 'fact' even without choice. Rather, it would be correct to say that there are models of ZF where there exist graphs of the relevant sort; after all, ZFC still includes all the axioms of ZF, so it's not like these graphs magically 'evaporate' when you add axioms! As for why they're not studied much, I would hazard to say that it's because models of ZF that don't even satisfy countable choice are wild and wooly places where even the most seasoned set theorists tread carefully, and as such are inappropriate to an introduction to the subject. – Steven Stadnicki Feb 20 '14 at 18:47
And since any 'missing graph' (I would prefer to say counterexample) must of necessity be an inhabitant of such a wild and wooly place, they're very hard to exhibit explicitly, as pretty much all choice-incompatible objects are. – Steven Stadnicki Feb 20 '14 at 18:50
@Steven Stadnicki, Yes my point is that after searching Graph theory texts no reference is found to these kind of "counter-examples" - so the stated Graph Theory theorems are often not correct. By "ZFC theory" in the penultimate para I am refering to the "ZFC-Graph Theory" I mentioned earlier. So my question is really directed at standard Graph Theory (and its definitions, examples and "theorems") rather than models of Set Theory, per se. – Roy Simpson Feb 20 '14 at 19:29
Graph theorists seem to prefer Finite graphs - and may find Infinite graphs a bit wooly in the first place. But their theorems need to be correct for that domain, nevertheless. – Roy Simpson Feb 20 '14 at 19:38
Roy, I very much agree with @Steven's point. And I have said so repeatedly -- the failure of the axiom of choice is as non-constructive as the axiom of choice itself. So in order to know how things can fail, you need to understand more thoroughly the various degrees of failure the axiom of choice may have and the intricate relations between these varying degrees of failure. And so talking about graph theory without the axiom of choice would effectively require you to make a lot conditional statements which are harder to parse. – Asaf Karagila Feb 20 '14 at 19:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.