0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Nov 30, 2021 at 14:59
  • $\begingroup$ 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 $\endgroup$ Commented Nov 30, 2021 at 15:22
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Nov 30, 2021 at 15:59

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ In fact, this same argument implies that there must be a vertex with uncountable degree, right? $\endgroup$ Commented Nov 30, 2021 at 23:14
  • $\begingroup$ @MishaLavrov Hmm, not sure about that... maybe it only needs a countable infinity of vertices with countable infinite degree. $\endgroup$
    – Joffan
    Commented Nov 30, 2021 at 23:51
  • $\begingroup$ '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. $\endgroup$
    – Riemann
    Commented Jun 6, 2023 at 11:45
  • 1
    $\begingroup$ @Riemann true, thanks for pointing it out. That defeats my attempt to put a limit on the number of nodes at a given distance from the arbitrary start node, but doesn't change the fact that those nodes are a finite set, so can be counted block by block. $\endgroup$
    – Joffan
    Commented Jun 15, 2023 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .