# Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question:

Prove that any directed cycle in the graph of a partial order must only involve one node.

So I know that a partial order must be transitive, antisymmetric, and reflective, but from there I am pretty lost. I also know that any path of one or more edges from a node to itself is a directed cycle, but from there I am having trouble connecting everything.

I kind of need help as to where to start thinking, and the first step as to how to answer this question.

• Follows directly from transitivity and antisymmetry, doesn't it? – G. Bach Oct 24 '13 at 2:09

I'm assuming your partial orders are of the type "$a \leq b$" rather than of the type "$a < b$", though the proof is very similar to both cases. Each edge $a \to b$ in the graph corresponds to an inequality $a \leq b$. Now suppose you had a triangle $a \to b \to c \to a$. Such a triangle would imply $$a \leq b \leq c \leq a,$$ which has some implications since $\leq$ is a partial order. The case of longer (or shorter) cycles is similar.
• In a partial order, all nodes in a strongly connected component are all equally related; because there is a path from every node to every node: due to the transitive property, this means that $a \le b \wedge b \le a$ for all $a,b$ in the strongly connected component.
This can contradict the antisymmetric property. "More formally, R is antisymmetric precisely if for all a and b in X: if R(a,b) and R(b,a), then a = b, or, equivalently, if R(a,b) with a ≠ b, then R(b,a) must not hold." - wikipedia. It requires that: iif two nodes are equally related to eachother, that they are the same node. Thus, if a cycle contains more than one node, there are two nodes that are equally related ($a\le b, b\le a$), yet not the same ($a \ne b$). If the cycle is one node, then it is equal to itself and the same and thus the antisymmetric property holds.