Trying to prove that G is a bipartite graph...

Question

Suppose I have directed graph $G=(V,E)$ s.t at least one of the following statements is always true:

1. for every $v$ in $V$, v doesn't have any incoming edges.
2. for every $v$ in $V$, v doesn't have any outgoing edges.

How can I prove that G is bipartite? I tried to think of a proof but coldn't figure it out.

Answer 1

HINT: Let $V_0$ be the set of vertices with no incoming edge and $V_1$ the set of vertices with no outgoing edge.

Answer 2

Your current statement is:

Suppose I have directed graph $G=(V,E)$ s.t. at least one of the following statements is always true:

1. for every $v$ in $V$, $v$ doesn't have any incoming edges.
2. for every $v$ in $V$, $v$ doesn't have any outgoing edges.

Any directed edge is an incoming edge for one of its endpoints and outgoing for the second of its endpoints. Thus, existence even of a single edge violates both (1) and (2). In other words, both (1) and (2), as currently stated, imply independently that there are no edges in the graph. Such a graph is certainly bipartite.

I hope this helps $\ddot\smile$