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

Improve this question
$\endgroup$
3
  • $\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
    Commented Sep 5, 2018 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
    Commented Sep 20, 2018 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
    Commented Sep 20, 2018 at 12:14

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .