Can I use mathematical induction here?

38 Views Asked by At

Given any digraph $D=(V,E)$ such that for every finite subset $S\subseteq V$ there exists a vertex $v_{S}\in V$ capable of reaching any vertex in $S$ via a directed path.

Can one deduce there is a vertex $u\in V$ capable of reaching any vertex in $V$ via a directed path?

Do I have to assume $V$ itself is finite for this to work? Or can I make this deduction irregardless of the cardinality of $V$? I know if I have two subsets $A,B\subseteq V$, where every vertex in $A$ is reachable by $v_{A}$ and every vertex in $B$ is reachble by $v_B$ then, since $\{v_{A},v_{B}\}\subseteq V$ there must exist a vertex $u$ capable of reaching both $v_A$ and $v_B$ which means $u$ is capable of reaching every vertex in $A\cup B$.

1

There are 1 best solutions below

0
On BEST ANSWER

No, you can't deduce that such a vertex $u$ exists.

Consider the graph with vertex set $\mathbb Z$, and an edge from $n$ to $n+1$ for every $n \in \mathbb Z$.

Then for every finite set $S$, the vertex $\min S$ can reach any vertex in $S$. However, for every vertex $n$, there are vertices (such as $n-1$) that can't be reached from $n$.

(On the other hand, if $V$ is finite, then the statement is - trivially - true. In that case, $V$ itself is a finite subset of $V$.)