Prove that there is an orientation of $G$ in which no directed path has length $2$ if and only if $g$ is bipartite.

389 Views Asked by At

Let $G$ be a graph of order $n\geq3$. Prove that there is an orientation of $G$ in which no directed path has length $2$ if and only if $G$ is bipartite.

I don't know if I understand this correctly, but some bipartite for instance $W_{2,3}$ can have a directed path length 2.

2

There are 2 best solutions below

2
On BEST ANSWER

The question is not saying that all orientations of a bipartite graph must have no directed paths of length $2$, just at least one does.

For this question, think about cycles in the (undirected) graph. Can you orient the edges of an odd cycle so that no consecutive edges have the same orientation?

On the other hand, think of the common drawing of a bipartite graph as having two sides, with all edges going between the two sides. With this picture in mind, can you see a way to orient the edges that guarantees only directed paths of length $0$ or $1$ exist?

0
On

As Casteels said, there is an obvious orientation of the edges of a bipartite graph that has no directed paths of length 2. On the other hand, suppose you have an oriented graph $G$ with no directed path of length 2. Then every vertex $v$ of $G$ has either in-degree 0 or out-degree 0, for otherwise there is a path of length 2 through $v$. The sources and sinks in $G$ give a bipartition of the vertices.