Talk:Tournament (graph theory)

"undirected"

The intro says the graph is undirected, but the image directly below that statement shows a directed graph. Please fix. --AlanH (talk) 18:36, 22 February 2008 (UTC)

Nope, the intro says that a tournament is a graph obtained by assigning direction to edges of a complete undirected graph, thus making it a directed graph. --Rulatir (talk) 20:21, 5 July 2009 (UTC)

largest transitive subtournament

"Every tournament on n vertices has a transitive subtournament on log2n vertices. Reid and Parker showed that this is the best possible result: there exist n-vertex tournaments whose largest transitive subtournament is of size log2n."

This comes with no reference, and is apparently simply wrong. I belive the best known upper bound is ~2log2n. —Preceding unsigned comment added by 132.64.140.208 (talk) 11:46, 24 November 2010 (UTC)

Last Sentence Paths and Cycles

It reads: "Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980)."

Aren't all tournaments complete graphs? Isn't a complete graph with k vertices always k-connected? Therefore wouldn't it be simpler to write, "Moreover, if the tournament has 4 or more vertices, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980)." —Preceding unsigned comment added by Recurve7 (talk • contribs) 19:28, 25 November 2010 (UTC)

It's a directed form of connectivity. I imagine that it means that it remains strongly connected after the removal of any three vertices, but I'd have to check the source to be sure. —David Eppstein (talk) 19:49, 25 November 2010 (UTC)

A UCI ICS grad's question fielded by a UCI CS professor on a random obscure Wikipedia Talk page. That's almost a graph theory connectedness anomaly in itself. -Recurve7