1
$\begingroup$

If $G=(V,E)$ is a finite, simple, undirected graph, then by $\eta(G)$ we denote the maximum integer $n\in \mathbb{N}$ such that $K_n$ is a minor of $G$. If $e\in E$ we write $G\setminus e$ to denote the graph $(V, E \setminus \{e\})$.

Is there a finite graph $G=(V,E)$ and $e\in E$ such that $\eta(G\setminus e) < \eta(G)-1$?

$\endgroup$

1 Answer 1

6
$\begingroup$

No, there is no such graph. Suppose $\eta(G)=n$. Let $T_1, \dots, T_n$ be a collection of vertex disjoint trees in $G$ such that for all distinct $i,j \in [n]$, there is an edge $e(ij) \in E(G)$ between $T_i$ and $T_j$. Consider an arbitrary edge $e \in E(G)$. If $e=e(ij)$ for some $i,j$, then removing $T_i$ (or $T_j$) yields a model of $K_{n-1}$ in $G \setminus e$. If $e \in E(T_i)$ for some $i$, then removing $T_i$ yields a model of $K_{n-1}$ in $G \setminus e$. Otherwise, $\eta(G \setminus e) = n$.

$\endgroup$
1
  • $\begingroup$ Thanks Tony for this great argument! $\endgroup$ Commented Feb 17, 2020 at 18:21

You must log in to answer this question.

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