Complete minors in a "redoubled" graph

Question

For any finite, simple, undirected graph $G=(V,E)$ denote by $G_2 = (V_2, E_2)$ the graph, in which $V_2$ and $E_2$ are defined as follows:

1. $V_2 = \big(V\times\{1\}\big) \cup \big(V\times \{2\}\big)$, and

2. $E_2 = \big\{\{(x,i),(y,i)\} : \{x,y\} \in E \textrm{ and } i \in \{1,2\}\big \} \cup \big\{\{(v,1), (w,2)\} : v,w\in V\big\}$.

In informal terms, $G_2$ consists of two copies of $G$ such that every vertex in one copy is connected to every vertex in the other copy.

Is there an example of a graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ such that

• $K_n$ is no minor of $G$, but
• $K_{2n}$ is a minor of $G_2$

?

Answer 1

There are more involved counterexamples than the one in the comments (an empty graph on three vertices with $n = 2$), in fact there are examples for any $n \in \mathbb{N}$. Let $G = (V, E)$ be a graph on $n + 1$ vertices with $E = {[n] \choose 2} \backslash \{12\}$. Clearly, $G$ has no $K_n$ minor. On the other hand, $G_2$ has $K_{2n}$ minor on the vertex set $S = \{(1, 1), \ldots, (n, 1), (1, 2), \ldots, (n, 2)\}$. All pairs of vertices in $S$ are adjacent except $(1, 1), (2, 1)$, and $(1, 2), (2, 2)$, but we can connect them $(1, 1) - (n + 1, 2) - (2, 1)$ and $(1, 2) - (n + 1, 1) - (2, 2)$, obtaining a proper subdivision of $K_{2n}$.

The gap $2$ between complete minor sizes of $G$ and $G_2$ can be, in fact, increased arbitrarily, since for any $n$ the empty graph with $n + {n\choose 2}$ vertices does not have $K_2$ minor, but the join of two such graphs $= K_{n + {n \choose 2}, n + {n \choose 2}}$ has $K_{2n}$ minor (use $n \choose 2$ vertices of one half to connect each pair of $n$ vertices in the other half).