Points connected by vectors

34 Views Asked by At

I need a proof of the following assertion, if any:

Let there be n points on a plane, where n∈ℕ≥2. None of these points lie on the exact same location. Vectors are placed such that every point is connected with every other point via a vector. Whatever way these vectors are pointing, it is always possible to start at one point, and follow the vector starting at that point,to the next point, and carry out this prossess until you have been at every single point. (Needs to hold for all natural numbers greater than or equal to 2).

If you don't understand what i am asking for, here is the same problem formulated differently:

Given n water tanks, all mutually connected with water pipes, where each and all water pipes have a valve allowing water to flow trough in only one direction,(direction not given). Prove that it is always possible for water to flow trough all water tanks through a path of pipes, starting at some water tank.

Robin.

1

There are 1 best solutions below

0
On

The assertion is equivalent to:

In a complete graph $K_n$ with all edges directed (aka tournament), there exists a Hamiltonian path.

The proof is classical, and I summarise the one given on Wikipedia. If the assertion holds for all n-vertex tournaments, a path in an n-vertex subgraph of any (n + 1)-vertex tournament can always have the excluded vertex inserted into itself, and the assertion is true for (n + 1)-vertex tournaments. Obviously the n = 2 case always has a Hamiltonian path, and the proof follows by induction.