Combinatorics and Graph Theory · Problem 5.11.3

Graph Theory — David Guichard

Mathematics — Combinatorics · tournaments-hamilton-path

Problem

A tournament is an oriented complete graph. That is, it is a digraph on nn vertices, containing exactly one of the arcs (v,w)(v, w) and (w,v)(w, v) for every pair of vertices. A Hamilton path is a walk that uses every vertex exactly once. Show that every tournament has a Hamilton path.

Browse the problem library