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$

Additional note

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


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}$.)

The situation described

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.

| cite | improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – prometheus21 Nov 4 '15 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.