# Directed graph, partition

Let $D=(V,E)$ be a finite directed graph with no isolated nodes(from every node there is at least one edge entering and one exiting, i.e there are no sources or sinks). For $v \in V$ define the following sets: $$v^+= \left\{w \in V|(v,w)\in E \right\}, v^-= \left\{w \in V|(w,v)\in E \right\}$$

For some $S \subseteq V, S^+= \bigcup_{v \in S} v^+, S^-= \bigcup_{v \in S} v^-$

Now define two related graphs, $G_{cp}=(V,E_{cp}),G_{ce}=(V,E_{ce})$ such that for two distinct nodes $v,w \in V$ we have $vw \in E_{cp}$ iff $v^+ \cap w^+ \neq \emptyset$ and $vw \in E_{ce}$ iff $v^- \cap w^- \neq \emptyset$ Let $B_1,B_2,...,B_p$ be the sets of nodes of the connected components of $G_{cp}$ and $A_1,A_2,...,A_k$ be the set of connected components of $G_{ce}$. Obviously those sets are two partitions of $V$

Prove that $(B^+_1,B^+_2,...,B^+_p)$ and $(A^-_1,A^-_2,...,A^-_k)$ represent partitions of $V$. Also prove that $p=k$ (that is both graphs have the same number of connected components).

To prove the first part I thought about taking some arbitrary $v \in V$ and than proving that $v$ is in $(B^+_1,B^+_2,...,B^+_p)$. Then a proof by contradiction may be required to complete the first part, but I can't quite seem to make the connection. I don't even know how to start proving $p=k$

The notation cp and ce comes from "common prey" and "common enemy"

Update

I managed to sketch a proof for the first part along the lines I talked about. Proof by contradiction works. I still need help in proving $p=k$

(I am completely changing this answer, given that every node has both incoming and outgoing edges.)

First, we show that $\{B_1^+, \dotsc, B_p^+\}$ is a partition of $V$. If a vertex $v$ is in two of these sets, say $v \in B_1^+ \cap B_2^+$, then there is an edge from some $x \in B_1$ to $v$, and an edge from some $y \in B_2$ to $v$. Then $x$ and $y$ share the common prey $v$, so there is an edge in $G_{cp}$ from $x$ to $y$, contradicting that they are in different connected components of $G_{cp}$.

Thus, the sets $B_i^+$ are disjoint. Each set is nonempty, because all vertices have outgoing edges. Every vertex is one of these sets, since all vertices have incoming edges (and the sets $B_i$ form a partition.)

An entirely similar proof shows that the sets $A_1^-, \dotsc, A_k^-$ form a partition of $V$.

Now we prove that each set $B_i^+$ is actually one of the sets $A_j$. Suppose that $u$ and $v$ are two vertices in $B_1^+$. We will show that they are in the same connected component of $G_{ce}$. If $u$ and $v$ are both prey to the same vertex in $B_1$, then they share a common enemy, hence are adjacent in $G_{ce}$. Otherwise, let $b_1, b_t \in B_1$ such that there is an edge from $b_1$ to $u$, an edge from $b_t$ to $v$, and there is a path in $G_{cp}$ from $b_1$ to $b_t$ of minimal length, going from $b_1, b_2, \dotsc, b_t$. (This path must exist since $B_1$ is a connected component of $G_{cp}$.)

In this figure, black edges are in $D$, red edges are in $G_{cp}$, and blue edges are in $G_{ce}$. Given the solid edges, we conclude that the dashed edges must exist.

Because $b_1$ and $b_2$ are adjacent in $G_{cp}$, they share a common prey, say $u_1$ (this cannot be $u$, since otherwise we would find a shorter path of $b_i$s.) Then $u$ and $u_1$ share a common enemy of $b_1$, hence are adjacent in $G_{ce}$. Proceeding, because $b_i$ and $b_{i+1}$ are adjacent in $G_{cp}$, they share a common prey $u_i$ (which is distinct from all the previous $u_j$, since otherwise we could find a shorter path.) Then $u_{i-1}$ and $u_i$ share a common enemy of $b_i$, hence are adjacent in $G_{ce}$. Finally, having constructed a path from $u$ to a node $u_{t-1}$ which is common prey to $b_{t-1}$ and $b_t$, we see that $u_{t-1}$ is adjacent to $v$ in $G_{ce}$ since $b_t$ is an enemy to both.

Therefore $u$ and $v$ are in the same connected component of $G_{ce}$. This proves that each set $B_i^+$ is contained in one of the sets $A_j$. Since the collection $\{B_1^+, \dotsc, B_p^+\}$ and $\{A_1, \dotsc, A_k\}$ are both partitions, and all the sets in one are contained in sets of the other, the sets must in fact coincide: thus there is a bijection from the $B_i$s to the $A_j$s and so $p = k$.

A similar argument shows that each $A_j^-$ is one of the sets $B_i$. The maps $B_i \mapsto B_i^+$ and $A_j \mapsto A_j^-$ are mutually inverse bijections.

• You are correct, it has a stronger meaning. From every node there is at least one edge entering and one exiting. I will update the problem – prometheus21 Nov 4 '15 at 6:31