How to prove vertex basis?

Question

If $G = (V, E)$ is a simple, directed and acyclic graph. How can we prove that $B = \left\{{v \in V | d^-(v) = 0}\right\}$ is a vertex basis of G, and moreover it is the only vertex basis?

Please note that $d^-(v)$ is the in-degree of the vertex.

EDIT:

Let $G = (V, E)$ be a simple, directed and acyclic graph. $\exists v \in V$, such that $d^-(v) = 0$, by the definition of vertex basis, this implies that $v \in B$ ($v$ is a vertex basis).

Let $v \in V \setminus B$, and we walk back from $v$ by traversing edges against their orientations. Using this process, we either reach a vertex in $B$, or a vertex previously reached. The latter part implies that there is a cycle and that $G$ is a cyclic graph, which contradicts our definition of G.

Answer 1

HINT: First show that every vertex of in-degree $0$ must belong to every vertex basis; this is immediate from the definition of vertex basis. Then let $v\in V\setminus B$, and ‘walk back’ from $v$ by traversing edges against their orientations. Show that this process must either reach a vertex in $B$, in which case $v$ is reachable from $B$, or return to a vertex previously reached; why is the latter impossible? This shows that $B$ is a vertex basis and is a subset of every vertex basis for $G$. Finally, use the ‘walking back’ argument to show that no vertex basis for $G$ can contain any vertex not in $B$.

Added in response to the edit: I gather that the first paragraph is an attempt to show that $B$ must be a subset of every vertex basis, but it doesn’t actually do that. To do that, you want to suppose that some $C\subseteq V$ is a vertex basis for $G$, let $v\in B$, and prove that $v\in C$. Suppose that $v\notin C$; then since $C$ is a vertex basis, there is a directed path from some $u\in C$ to $v$. But that means that the in-degree of $v$ is at least $1$, contradicting the assumption that $v\in B$. Thus, $v\in C$, and since $v$ was an arbitrary vertex of $B$, we’ve shown that $B\subseteq C$. That is, $B$ is a subset of every vertex basis for $G$.

In the second paragraph you need to justify the assertion that we reach either a vertex of $B$ or a vertex previously reached. I suggest organizing it as follows:

Now we want to show that every vertex of $G$ is reachable from $B$. Let $v_0\in V\setminus B$. Since $v_0\notin B$, $\deg^-(v_0)\ge 1$, and there is a vertex $v_1$ such that $\langle v_1,v_0\rangle$ is an edge of $G$. If $v_1\in B$, we’ve shown that $v_0$ can be reached from $B$. If not, $\deg^-(v_1)\ge 1$, and there is a vertex $v_2$ such that $\langle v_2,v_1\rangle$ is an edge of $G$. Again, if $v_2\in B$, we have a path from $B$ to $v_0$, namely, $v_2,v_1,v_0$. If not, continue. If at any point we reach a vertex in $B$, we’re done: following the vertices in the opposite order gives us a path from $B$ to $v_0$.

Now explain why the only other possibility (besides reaching a vertex of $B$) is reaching a $v_k$ that you’d previously reached, so that you have a directed cycle, contrary to the hypothesis that the graph is acyclic. You should probably then explain why no vertex of $B$ is reachable from any other vertex of $B$; admittedly it’s pretty obvious, but play safe by mentioning it explicitly. Then you’ve proved that $B$ is vertex basis for $G$. Uniqueness is implicit in what’s already been proved, but again you should probably make it explicit.

Suppose that $C$ is a vertex basis for $G$. We’ve shown that $B\subseteq C$. We’ve also shown that if $v\in V\setminus B$, then $v$ can be reached from $B$ and hence from $C$; by the definition of vertex basis this means that $v$ cannot be a member of $C$, so $C\cap(V\setminus B)=\varnothing$, and therefore $C\subseteq B$. Putting the pieces together, we see that $B=C$ and hence that $B$ is the unique vertex basis for $G$.