2
$\begingroup$

Is there an infinite, simple, undirected graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ with the following properties?

  1. $K_n$ is a minor of $G$, but $K_{n+1}$ is not a minor of $G$, and
  2. if $F$ is a finite subgraph of $G$, then $K_n$ is not a minor of $F$.

(Note: I use "compactness" in the title because this question has certain parallels with the compactness result of Erdös-De Bruijn.)

$\endgroup$
  • $\begingroup$ Sorry, I do not understand. How can $K_n$ (or any finite graph) be a minor of $G$, but not of any its finite subgraph? $\endgroup$ – Ilya Bogdanov Sep 5 '18 at 13:55
  • $\begingroup$ Indeed, it seems to me that the minor $K_n$ is determined by $n$ connected sets of vertices and $n(n-1)/2$ paths though $G$. Each path has finitely many edges and if we only use the points incident with those edges and enough edges and vertices in each of the $n$ connected sets to make a connected graph then $K_n$ is a minor of the resulting finite graph. $\endgroup$ – KP Hart Sep 20 '18 at 10:23
  • $\begingroup$ @KPHart and Ilya Bogdanov I think both your arguments are valid, can any one make an answer of the argument so we can close the thread? $\endgroup$ – Dominic van der Zypen Sep 20 '18 at 12:14
1
$\begingroup$

Assume $K_n$ is a minor of $G$. Each vertex of $K_n$ corresponds to a connected subset of vertices of $G$ as it can only have been obtained by contracting edges. Each edge of $K_n$ can only have been derived from a path through $G$, by contracting edges. Now create $F$ as follows: collect the edges of the $n(n-1)/2$ paths and the vertices incident to these, this gives of finite subsets of the aforementioned connected sets that gives us the vertices of $K_n$. Add finitely many edges to make these finite sets connected. The resulting graph has $K_n$ as a minor. This means that condition 2 in the question can not be met.

$\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.