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.
Best Answer
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.
Note that given both a maximum vertex degree and a maximum path length, a connected graph is necessarily finite.