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.