I was looking at the Hadwiger Conjecture and the four color theorem, and tried to get a better grasp of what it really means to have a complete graph as minor. I wondered whether the following three statements are equivalent.
Let $G =(V, E)$ be a simple graph.
A). $G$ has the compleet graph $K_n$ as a minor
B). There exist a subset $V'\subset V$ containing n vertices, so that for each pair of vertices in $V'$, there exists a path connecting them, without crossing any third vertix of $V'$, and so that none of the $n*(n-1)/2$ paths intersect with another. (except for having a mutual start or end point).
C). There exist a subset V* containing n vertices, so that for each (of the $n!$ possible) orderings on the vertices of V*, there exist a path, that visits all vertices of V* in the given order.
It's obvious that B implies C if we define $V* = V'$. Furthermore, B implies A because we end up with $K_n$ if we contract all paths between pairs of V', and delete all other vertices and edges.
C appears to be weaker than B, but not sure.
Thanks for your time
I re-read my answer, and my first statement was wrong. I corrected my answer:
A) and B) are not equivalent
A) is weaker than B) Let's take $K_5$. Let's take one of the vertices (of degree 4) and split it into two vertices of degree 2 (by distributing the four adjacent edges) and link these two vertices by an edge. (so these vertices are degree 3). Obviously, this graph admits $K_5$ as a minor because contracting the added edge gives back $K_5$, but we can't find the $n(n-1)/2$ disjoint paths because we need to find four vertices of degree at least 4, which is not possible
C) is weaker than B): We can take $K_{n,n-1}$ with $V^*$ the set of vertices on one side of $K_{n,n-1}$. It is obvious that for each ordering on the vertices of $V^*$, there exists a path that visits all vertices of $V^*$ in the given order. For $n$ sufficiently large, B) will not be verified. We have to find $\frac{n(n-1)}{2}$ disjoint paths. We have at most $\left(\frac{n}{2}\right)^2$ paths of length 1 (if we distribute equally the $n$ vertices of $V'$ on both sides of $K_{n,n-1}$), so it remains a quadratic number of disjoint paths to find. There can be at most $n-1$ disjoint paths of length 2, because each path consumes at least on vertex outside of $V'$. This is not sufficient to get a quadratic number of disjoint paths.
Here is a graph that satisfy C) but not A) Take the graph of a hexagonal bipyramid (take two pyramids of pentagonal base and glue them by the base). It is planar, so by Wagner theorem, it does not have $K_5$ as a minor. Yet, if we let $V^*$ be the set composed of the two apices and three non-adjacent vertices of the hexagonal base, we can easily verify that we can find a path through any order of these 5 vertices.
Here is a graph that satisfy A) but not C) The Peterson graph admits $K_5$ as a minor. However, it does not satisfy C). It can be a bit tedious to check this, here how I did it rather concisely: We take the petersen graph in its classical representation, with a star inside a pentagon. Let $V^*$ be a set of vertices of sze $5$. We know that either the pentagon or the star contains at least 3 vertices of $V^*$. Because there is an automorphism exchanging the pentagon and the star, we can suppose WLOG that the pentagon has at least 3 vertices of $V*$. Lets number vertices of the pentagon $1,2, ..., 5$ in the clockwise order, and vertices of the star $a, b, ..., e$ in the clockwise order, so that $1$ is adjacent to $a$ (and $2$ is adjacent to $b$, ...).
Suppose the pentagon have 3 consecutive vertices in $V^*$ (WLOG, 1, 2 and 3). It is impossible to find a path of the form $13x2x$ (where $x$ can denotes any other vertices), so C) is not verified. Thus the pentagon must have 3 non-consecutive vertices (WLOG 1,2 and 4). Suppose $a$ is in $V*$. Any path of the form $4a21x$ is impossible, so $a$, (and by symetry $b$) are not in $V^*$.
Two non-equivalent cases remain for $V^*$: $\{1, 2, 4, c, d\}$ and $\{1, 2, 4, c, e\}$, and are ruled out by the orders $14c2d$ and $1e42c$. (Technically, we can argue these two cases are equivalent under graph automorphism, but its harder to find).