0
$\begingroup$

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$

?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ A simple counterexample is $G = (V, \varnothing)$ with $|V| = 3$ which contains no $K_2$ minor, but $G_2 = K_{3, 3}$ has $K_4$ minor. $\endgroup$ – Mikhail Tikhomirov Nov 22 '17 at 16:31
2
$\begingroup$

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).

| cite | improve this answer | | | | |
$\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.