2
$\begingroup$

Let G be a directed graph such that every two vertices are connected by a single edge. How do I proof that such G has an hamiltonian path?

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! What have you tried? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. You might start by working through a few examples (see what happens when there are 2 vertices, then 3 vertices, then when there are 4 vertices, etc., and see if youc an spot a pattern). $\endgroup$ – D.W. Apr 16 '17 at 17:19
  • 1
    $\begingroup$ Note that such a graph is called a tournament. $\endgroup$ – David Richerby Apr 16 '17 at 23:53
4
$\begingroup$

Proof by induction

Basis. All complete oriented digraphs with two vertices have Hamiltonian path - it's obvious.

Induction step. Let's assume that complete oriented digraph $G_{n-1}$ with $(n - 1)$ vertices contains Hamiltonian path $(s, ..., t)$ from vertex $s$ to vertex $t$. We'll show how to build Hamiltonian path for complete oriented digraph $G_n$, which is constructed from $G_{n-1}$ by adding a vertex $p$.

Case 1. The $G_n$ has an edge $(p, s)$. The Hamiltonian path in $G_n$ will be $(p, s, ..., t)$.

Case 2. The $G_n$ has an edge $(s, p)$. Then we need to scan the Hamiltonian path $(s, ..., t)$, trying to find an edge $(v_{i-1}, v_i)$, such that the graph $G_n$ contains edges $(v_{i-1}, p)$ and $(p, v_i)$. There are two subcases:

Subcase 2.1. We can find such a pair - then the new Hamiltonian path will consist of three parts - $(s, ..., v_{i-1})$, $(v_{i-1}, p, v_i)$ and $(v_i, ..., t)$.

Subcase 2.2. We can't find such a pair - it means, that all the edges from vertices on the path $(s, ..., t)$ to the additional vertex $p$ are oriented to this vertex. The new Hamiltonian path will be $(s, ..., t, p)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.