        \problemdata       % Takes 5 *mandatory* arguments
        {poset-no-cycles}             % latex-friendly label for the prob.
        {graphs}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 PS4-1} % Usage (list ones you are aware of).
        {Ashish, S02}        % Last revision info (author, date).


\begin{problem}

Let G be the digraph for a partial ordered set $(S,P)$. In other words,
$S$ is the set of nodes and $a,b\in S$ are connected via a directed edge iff
$aPb$. Prove that G cannot contain any cycles of length $>1$.

\solution{ 
  Suppose $G$ contains a cycle $\langle v_1, v_2...  v_n, v_1\rangle$ where
  $n\geq 2$ and there are directed edges connecting $(v_1, v_2), (v_2,
  v_3)$ etc. as well as $(v_n, v_1)$.  We show that this leads to a
  contradiction.
  
  It can inductively be seen that $(v_1, v_i)$ is an edge in $G$ for
  any $2\leq i\leq n$.  Base case: $v_1Pv_2$ by hypothesis.  Inductive
  step: suppose $v_1Pv_i$ for some $i<n$.  Also, $v_iPv_{i+1}$ by
  hypothesis and using transitivity, it follows that $v_1Pv_{i+1}$.

From the above proof, we can conclude as a special case that
$v_1Pv_n$.  However, these vertices are in a cycle and $v_nPv_1$ by
hypothesis.  Also, since the cycle contains more than one element,
$v_1\neq v_n$.  These statements contradict the antisymmetry property
of a partial ordering.
}
\end{problem}
