# Show that every bipartite graph is a comparability graph.

Show that every bipartite graph is a comparability graph. A graph $$G$$ is a comparability graph if $$G$$ has a trasitive orientation $$D$$.

Well I'm a little confuse because I remember taht bipartite graphs can't have cycles of odd length and transitivity implies that we got a cycle of length $$3$$. I think I´m missing something here. Any hints?

• I think your issues are with the (false) converse: "Every comparability graph is bipartite". But, your observation is very revealing nonetheless. Certainly if you have vertices $a, b, c$ connected like so $a \to b \to c$, then we get a triangle $a \to c$. So, if you orient your graph, you'll have to have every vertex be either a source or a sink. Commented Mar 16, 2020 at 1:14
• Your bipartite graph has disjoint vertex sets $V_1$ and $V_2$ such that every edge joins a vertex in $V_1$ to a vertex in $V_2$. If each edge is directed from the endpoint in $V_1$ to the endpoint in $V_2$, is not that a transitive orientation???
– bof
Commented Mar 16, 2020 at 4:06
• @user759562 can you put that into an answer?
– SK19
Commented Mar 16, 2020 at 14:43

Just to formalize what was stated in the comments, this is completely obvious from the definitions: Let $$G$$ be a bipartite graph with bipartition $$(X, Y)$$. Recall that a graph is comparability if and only if it is transitively orientable; in simpler terms, this says that whenever we have a directed (not necessarily induced) $$P_3$$ (say $$a \rightarrow b \rightarrow c$$), we have $$ac \in E(G)$$, and moreover $$a \rightarrow c$$. For each $$xy \in E(G)$$ (where $$x \in X$$ and $$y \in Y$$), orient this edge as $$x \rightarrow y$$. This chosen orientation obviously does not have a directed $$P_3$$ ($$X$$ and $$Y$$ are both independent, and there are no edges from $$Y$$ to $$X$$ by choice), and hence is vacuously transitive by our above characterization. Since $$G$$ was arbitrary, this gives that any bipartite graph is comparability, as desired.