How might one label an infinite graph (which edges can cross over and all nodes are connected to at least 2 edges, such that there are no "dangling lines") to show that there are countably many such graphs, up to isomorphism/homomorphism? Thanks.
Cardinality of the set of graphs on a infinite set of vertices
-
1Surely there are uncountably many? I think it's pretty straightforward to construct an injection from $2^\mathbb{N}$ to such graphs. – 2011-08-19
1 Answers
There are uncountably many isomorphism types of undirected graph on a countable infinite set of vertices.
Ignoring for a moment the requirement of degree at least 2, starting from an infinite path one can single out a set of vertices corresponding to the natural numbers (such as the first vertex, then the third, then the fifth, and so on, or some other progression). Then, represent any subset of the positive integers by attaching a loop at the vertices corresponding to that subset. Satisfy the degree 2 condition by replacing loops by cycles of length 10. Finally, at the starting point of the infinite path, attach a cycle of length 20. This encodes every subset of the natural numbers as a unique isomorphism type of graph, so there are uncountably many.