If a tournament graph has no cycles of length $3$, prove that it is a partial order.
I was thinking that perhaps a proof by contradiction might helpful. Could I start with a tournament graph $G$ that has a cycle of $3$, assume that it is a partial order, and then find some contradiction/violation of the properties of a partial order (i.e. show that $G$ does not fulfill antisymmetry or transitivity)?
On
A binary relation $\lt$ is a (strict) partial order if it is irreflexive ($x\not\lt x$ for all $x$) and transitive (if $x\lt y$ and $y\lt z$ then $x\lt z$). It is a total order if it has the additional property of trichotomy: for all $x$ and $y$, either $x=y$ or $x\lt y$ or $y\lt x$.
Let $T$ be a tournament (finite or infinite), and let $x\lt y$ mean that there is an arc (directed edge) from $x$ to $y$. Irreflexivity and trichotomy follow immediately from the definition of a tournament: there are no loops, and each pair of distinct vertices is joined by an arc in just one direction.
Now suppose there are no (directed) $3$-cycles in $T$; we have to show that the relation $\lt$ is transitive. Suppose $x,y,z$ are vertices with $x\lt y\lt z$; we have to show that $x\lt z$. It follows immediately from the definition of a tournament that $x\ne z$. If $x\lt z$ did not hold, then $z\lt x$ would have to hold; and then the subgraph induced by $\{x,y,z\}$ would be a $3$-cycle, contradicting our assumption that there are no $3$-cycles in $T$.
You asked:
I was thinking that perhaps a proof by contradiction might helpful. Could I start with a tournament graph $G$ that has a cycle of $3$, assume that it is a partial order, and then find some contradiction/violation of the properties of a partial order (i.e. show that $G$ does not fulfill antisymmetry or transitivity)?
You could do that, but what that would prove is that a tournament which is a partial order can have no $3$-cycles, which is the converse of what you were asked to prove.
We shall prove a stronger claim that a finite tournament $G$ without directed $3$-cycle is a totally ordered set, where a vertex $u$ is less than another vertex $v$ if there exists an arc from $u$ to $v$. We prove by induction on the number of vertices $n$. The cases $n\in\{1,2,3\}$ are immediate. Suppose now that $G$ is a tournament on $n$ vertices with $n>3$ such that $G$ has no directed cycles of length $3$.
We first claim that there exists a vertex without an incoming arc or without an outgoing arc. Suppose on the contrary that every vertex of $G$ has both an incoming arc and an outgoing arc. This means $G$ has a directed cycle (because $G$ is finite). Suppose $v_1\to v_2\to \ldots \to v_k\to v_1$ is a directed cycle of $G$ with the lowest possible length.
Now, observe that there must exist an arc from $v_1\to v_3$ (otherwise, $v_1\to v_2\to v_3\to v_1$ is a directed $3$-cycle). If $k>3$, then $v_1\to v_3\to v_4\to\ldots\to v_k\to v_1$ is a smaller directed cycle, contradicting the choice of $v_1\to v_2\ldots \to v_k\to v_1$. Thus, $k=3$ and we end up with a directed $3$-cycle $v_1\to v_{2}\to v_3\to v_1$, which is a contradiction.
Now, we can remove a vertex $u$, either without an incoming arc or without an outgoing arc, to get a tournament $G'$ without directed $3$-cycles. By induction hypothesis, $G'$ is a totally ordered set. Adding $u$ to $G'$ either makes $u$ the smallest or the largest element of $G=G'\cup\{u\}$.
It is also true that an arbitrary (not necessarily finite) tournament $G$ without directed $3$-cycle is a totally ordered set. This is done by considering each finite subgraph $H$ of $G$ to construct a total order on $H$. Then, use a colimit argument to extend the ordering onto the whole $G$. This shows that $G$ is also totally ordered, with the same ordering as before: a vertex $u$ is less than another vertex $v$ if there exists an arc from $u$ to $v$.