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

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.

share|cite|improve this question
I see that the "counting" tag automatically changes to "combinatorics"...? – Marc Aug 19 '11 at 16:22
Surely there are uncountably many? I think it's pretty straightforward to construct an injection from $2^\mathbb{N}$ to such graphs. – Peter Taylor Aug 19 '11 at 17:53
up vote 1 down vote accepted

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.

share|cite|improve this answer
Thank you, zyx. – Marc Aug 19 '11 at 19:27

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.