Vertex sets separated only by infinitely many vertices imply an infinite number of disjoint paths between them.

71 Views Asked by At

In Reinhard Diestel's book "Graph Theory" (5th ed.) there is a chapter on infinite graphs (chapter 8).

In that chapter Diestel states the following fact related to Menger's Theorem:

Proposition 8.4.1 Let $G$ be any graph, $k \in \mathbb{N}$, and let $A, B$ be two sets of vertices in $G$ that can be separated by $k$ but no fewer than $k$ vertices. Then $G$ contains $k$ disjoint $A-B$ paths.

Directly below the proof of that proposition, he states:

When k is infinite, however, the result suddenly becomes trivial.

I interpret this as the following reformulation of the Proposition:

If two vertex sets $A$, $B$ of an (infinite) graph $G$ can not be separated by finitely many vertices, then $G$ contains infinitely many disjoint $A$-$B$ paths.

He then argues why that is:

Let $\mathcal{P}$ be any maximal set of disjoint $A-B$ paths in $G$. Then the union of all these paths separates $A$ from $B$, so $\mathcal{P}$ must be infinite. But then the cardinality of this union is no bigger than $|\mathcal{P}|$. Thus, $\mathcal{P}$ contains $|\mathcal{P}| = | \bigcup \mathcal{P} | \geq k$ disjoint $A-B$ paths, as desired.

I do not understand why we can immediately conclude that $\mathcal{P}$ is infinite in the second sentence. What if the number of disjoint $A-B$ paths is finite, but some of the paths are infinite? Then $\bigcup \mathcal{P}$ still contains an infinite number of vertices, including those which separate $A$ and $B$.

For example, there could be a non-disjoint set $\mathcal{Q}$ of $A-B$ paths that have an infinite number of distinct intersection vertices with some infinite paths of $\mathcal{P}$ while still only intersecting with finitely many paths of $\mathcal{P}$ in total.

I have been thinking about this for quite a long time and I suppose I am just missing some really obvious fact here. Maybe I should also point out that I have very little experience with infinite graphs and am still learning the basics of graph theory.

Maybe you can point me in the right direction?