Proof: Tournament is Transitive iff it has No Cycles | Graph Theory

We prove that a tournament graph is transitive if and only if it has no cycles. Recall a tournament is a directed graph with exactly one arc between each pair of vertices, and we say a tournament T is transitive if whenever (u,v), and (v,w) are arcs of T, (u,w) is an arc as well. We'll see in today's graph theory video lesson how a tournament being transitive is intimately connected to a tournament having no cycles. #GraphTheory

★DONATE★

Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!

Follow Wrath of Math on...

[mike_the_tutor]

Best graph theory playlist on YouTube. The previous title was held by the lesser-known Sarada Herke, but at this point your playlist is more comprehensive. I think your pacing has improved as well. Very nice explanation. Looking forward to more real analysis videos, or whatever you feel inspired to create. Keep it up my guy.

[DavidAmos]

Very nice! The explanation is super clear. I spent some time trying to come up with a direct proof for the transitive implies no cycles direction but didn’t get very far. More evidence that proving something is impossible is usually easier by contradiction!

[aashsyed]

Thanks so much!!!
I am so proud of you proud 🦚🦚!!!

[ODSD_EXCITEMENT]

Love you're methods and content. Please cover hypergraphs and multi graph

[alexanderpoddiakov]

Thank you very much. I would like to refer to a text with the proof (not to the video only). Is it published as a text?

[PunmasterSTP]

No cycles? More like "Nice videos!" 👍

[LearningCS-jpcb]

strange that i got the the first proof by myself and a bit exhausted to proof the easier one.