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$
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$
  • $\begingroup$ Thanks Tony for this great argument! $\endgroup$ – Dominic van der Zypen Feb 17 at 18:21

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.