An Euler tour is a walk in an undirected graph that traverses every edge exactly once and returns to its starting vertex; the fundamental characterization theorem states that a connected graph admits an Euler tour if and only if every vertex has even degree, proved via a degree-counting argument in one direction and a longest-walk extremal/contradiction argument in the other. The theory extends to directed graphs (digraphs), including in-degree/out-degree, adjacency matrices whose powers count directed walks of a given length (proved by induction), strong connectivity, and directed acyclic graphs (DAGs). Tournament graphs—complete directed graphs where every pair of vertices has exactly one directed edge—are shown by induction to always contain a directed Hamiltonian path, and the vertex of maximum out-degree is proved (by contradiction) to always be a "king" under the transitive-closure-like relation of virtual domination (reaching every other vertex within two steps).
An Euler tour is a walk in an undirected graph that traverses every edge exactly once and returns to its starting vertex; the fundamental characterization theorem states that a connected graph admits…