# Uncountable connected graph has an infinite degree vertex

I am reading Dixon's Permutation Groups book and am currently looking at the section about graphs. I am a bit stuck on the exercise 2.3.1 which basically asks to prove that if $$G$$ is a connected graph whose vertex set is uncountable, then there's a vertex with infinite degree. My attempt at the solution is the following:

Take an arbitrary vertex $$v$$. Since $$G$$ is connected, we can reach any other vertex in finitely many steps. Hence there's an integer $$n$$ such that any path from $$v$$ to any other vertex has length smaller than $$n$$. Also, since every vertex has a finite degree, if we run BFS on this graph from $$v$$, we will reach every vertex in finite amount of time, since each recursive call will be finite, and there will be at most $$n$$ such calls in "depth", which implies that there are finitely many vertices in this graph.

Now clearly I did something wrong, since I "proved" a stronger statement, namely that if $$G$$ is any connected infinite graph, it has a vertex of infinite degree, which is not true (I think), that is, I never used the fact that $$V(G)$$ is uncountable.

• Think of the graph of the integers with each one connected one above and one below. This is an infinite connected graph with no infinite vertex. Where does your proof fail? Commented Nov 30, 2021 at 14:59
• Right, so my assumption that all the paths are finite is wrong? So essentially, the only condition for a graph to be connected is that for any pair of vertices, there's a finite path between them? ie. I got my quantifiers in the wrong order :D Commented Nov 30, 2021 at 15:22
• Your assumption that the paths are finite is correct, but there is no upper bound to the length of the path. It is like all natural numbers are finite, but there is a countable infinity of them. On any given path there is an upper bound. Commented Nov 30, 2021 at 15:59

Your proof only needs a minor tweak to reflect the fact that there is no $$n$$ maximum path length available.
A graph that has no vertex of infinite degree has a maximum vertex degree, say $$d_{\small M}$$. This also means that, from a given vertex, the set of vertices at distance $$i$$, $$U_i$$ is finite; specifically $$|U_i| \le {d_{{}_M}}^i$$. We can thus number the vertices in blocks based on distance from an arbitrary start point, showing that the vertices are countable - a contradiction as required.
• 'A graph that has no vertex of infinite degree has a maximum vertex degree'. This is not true. We can for example let $G$ be the one-dimensional lattice and give vertex $n$ (for $n$ positive) an amount of $n$ extra children, which are not connected to any other vertex. Commented Jun 6, 2023 at 11:45