Unavoidable induced subgraphs in graphs with complete bipartite induced minors

Suppose that $A$ is not of type path. Let $P=x\dots z$ be a path in $A$ such that $x$ sees $X$, $z$ sees $Z$, $P\setminus x$ is anticomplete to $X$ and $P\setminus z$ is anticomplete to $Z$. Note that such a path exists (consider for instance a shortest path from the vertices that see $X$ to the vertices that see $Z$). Since $A$ is not of type path centered at $Y$, $P$ is anticomplete to $Y$. Let $Q=y\dots y^{\prime}$ be path in $A$ disjoint from $P$ and such that $y$ sees $Y$, $y^{\prime}$ sees $P$, $Q\setminus y$ is anticomplete to $Y$ and $Q\setminus y^{\prime}$ is anticomplete to $P$. Note again that such a path exists (consider for instance a shortest path from the vertices that see $Y$ to the vertices that see $P$). We suppose that $P$ and $Q$ are chosen subject to the minimality of $V(P)\cup V(Q)$.

Let $a$ be the neighbor of $y^{\prime}$ in $P$ closest to $x$ along $P$ and $a^{\prime}$ be the neighbor of $y^{\prime}$ in $P$ closest to $z$ along $P$ (possibly $a=a^{\prime}$ or $aa^{\prime}\in E(G)$).

If $Q$ sees both $X$ and $Z$, then consider vertex $u$ in $Q$ such that $yQu$ sees both $X$ and $Z$, and choose $u$ closest to $y$ along $Q$. The path $yQu$ shows that $A$ is of type path (centered at $X$ or $Z$, possibly both, possibly also centered at $Y$ if $u=y$), a contradiction. Hence, we may assume up to symmetry that $Q$ is anticomplete to $Z$. If $Q$ sees $X$, then the path $yQy^{\prime}a^{\prime}Pz$ shows that $A$ is of type path centered at $X$, a contradiction. Hence, $Q$ is anticomplete to $X$ and $Z$.

If $a\neq a^{\prime}$ and $aa^{\prime}\notin E(G)$, then consider the path $P^{\prime}=xPay^{\prime}a^{\prime}Pz$. If $y=y^{\prime}$, then because of $P^{\prime}$, $A$ is of type path centered at $Y$, a contradiction. So, $y\neq y^{\prime}$ and the paths $P^{\prime}$ and $Q\setminus y^{\prime}$ contradict the minimality of $V(P)\cup V(Q)$.

Hence $a=a^{\prime}$ or $aa^{\prime}\in E(G)$. If $a=a^{\prime}$, then the three paths $aPx$, $ay^{\prime}Qy$ and $aPz$ show that $A$ is of type claw with respect to $X$, $Y$ and $Z$. If $aa^{\prime}\in E(G)$, then the three paths $aPx$, $Q$ and $a^{\prime}Pz$ show that $A$ is of type triangle with respect to $X$, $Y$ and $Z$. ∎

Suppose for a contradiction that $A$ (the argument for $B$ is the same by symmetry) is not of type path with respect to $X$, $Y$ and $Z$. Hence, by Lemma 2.1, $A$ we may consider the two cases below.

If $B$ is of type claw, then there exist a vertex $b\in B$ and three paths $P^{\prime}=b\dots x^{\prime}$, $Q^{\prime}=b\dots y^{\prime}$ and $R=b\dots z^{\prime}$ like in the definition of type claw. Consider a shortest path $P^{\prime\prime}$ from $x$ to $x^{\prime}$ with interior in $X$, and let $Q^{\prime\prime}=y\dots y^{\prime}$ and $R^{\prime\prime}=z\dots z^{\prime}$ be defined similarly through $Y$ and $Z$. The nine paths $P$, $Q$, $R$, $P^{\prime}$, $Q^{\prime}$, $R^{\prime}$, $P^{\prime\prime}$, $Q^{\prime\prime}$ and $R^{\prime\prime}$ form a theta from $a$ to $b$, a contradiction.

If $B$ is of type triangle, a similar contradiction is found because of the existence of a pyramid in $G$.

So $B$ is not of type claw or triangle. By Lemma 2.1, $B$ is of type path, and up to symmetry we suppose that it is centered at $Y$. Let $P^{\prime}=x^{\prime}\dots z^{\prime}$ be a path like in the definition of type path. Consider a shortest path $P^{\prime\prime}$ from $x$ to $x^{\prime}$ with interior in $X$, and let $R^{\prime\prime}=z\dots z^{\prime}$ be defined similarly through $Z$. Let $Q^{\prime\prime}=b\dots b^{\prime}$ be a shortest path in $Y$ such that $by\in E(G)$ and $b^{\prime}$ sees $P^{\prime}$. Let $a^{\prime}$ be the neighbor of $b^{\prime}$ in $P^{\prime}$ closest to $x^{\prime}$ along $P^{\prime}$. Let $a^{\prime\prime}$ be the neighbor of $b^{\prime}$ in $P^{\prime}$ closest to $z^{\prime}$ along $P^{\prime}$. If $a^{\prime}=a^{\prime\prime}$, then $B$ is of type claw, a contradiction. If $a^{\prime}a^{\prime\prime}\in E(G)$, then the seven paths $P$, $Q$, $R$, $P^{\prime}$, $P^{\prime\prime}$, $Q^{\prime\prime}$ and $R^{\prime\prime}$ form a pyramid from $a$ to $b^{\prime}a^{\prime}a^{\prime\prime}$, a contradiction. Hence $a\neq a^{\prime}$ and $aa^{\prime}\notin E(G)$. So the paths $P$, $Q$, $R$, $x^{\prime}P^{\prime}a^{\prime}$, $a^{\prime\prime}P^{\prime}z^{\prime}$, $P^{\prime\prime}$, $Q^{\prime\prime}$ and $R^{\prime\prime}$ form a theta from $a$ to $b^{\prime}$, a contradiction.

The proof is almost the same as in Case 1, so we just sketch it. If $B$ is of type claw, then $G$ contains a pyramid. If $B$ is of type triangle, then $G$ contains a prism. And if $B$ is of type path, then $G$ contains a prism or a pyramid. ∎

Suppose for a contradiction that a 3PC-free graph $G$ contains $H=K^{*}_{2,3}$ as an induced minor. Denote by $a$ and $b$ the degree-3 vertices and let $ap_{1}p_{2}p_{3}b$, $aq_{1}q_{2}q_{3}b$ and $ar_{1}r_{2}r_{3}b$ be the three paths of $H$. Consider a minimal induced minor model $\{X_{v}\}_{v\in V(H)}$ of $H$ in $G$. For all $v\in V(H)\setminus\{a,b\}$, $v$ has two neighbors $u$ and $w$ in $H$ and by minimality, $X_{v}$ is a path $P=v^{\prime}\dots v^{\prime\prime}$ such that $v^{\prime}$ see $X_{u}$, $v^{\prime\prime}$ sees $X_{w}$, $P\setminus v^{\prime}$ is anticomplete to $X_{u}$ and $P\setminus v^{\prime\prime}$ is anticomplete to $X_{w}$. It follows that if we set $A=X_{a}\cup X_{p_{1}}\cup X_{p_{2}}\cup X_{q_{1}}\cup X_{q_{2}}\cup X_{r_{1}}\cup X_{r_{2}}$, $X=X_{p_{3}}$, $Y=X_{q_{3}}$, $Z=X_{r_{3}}$ and $B=X_{b}$, $A$ cannot be of type path with respect to $X$, $Y$ and $Z$. Indeed, since $X_{p_{1}}\cup X_{p_{2}}$, $X_{q_{1}}\cup X_{q_{2}}$ and $X_{r_{1}}\cup X_{r_{2}}$ all induce paths of length at least 1 in $G$, $A$ cannot contain a path with vertices seeing $X$, $Y$ and $Z$. Hence, $A$, $B$, $X$, $Y$ and $Z$ contradict Lemma 2.2. ∎

If a graph contains a $(5\times 5)$-grid as an induced minor, then it contains $K_{2,3}^{*}$ as an induced minor, because the $(5\times 5)$-grid contains $K_{2,3}^{*}$ as an induced subgraph. The result therefore follows from Lemma 2.3. ∎

First, for every neighbor $u$ of $v$ in $H$, let us mark a single vertex in $X_{v}$ that is adjacent to a vertex in $X_{u}$. If there exists a connected induced proper subgraph of $G[X_{v}]$ that contains all of the marked vertices, we contradict the minimality of the induced minor model.

Suppose that $G[X_{v}]$ contains a cycle of length longer than the degree of $v$, and let $C\subseteq X_{v}$ be the vertices of this cycle. We say that a vertex $w\in C$ is necessary if either $w$ is marked or there exists a connected component $Y$ of $G[X_{v}\setminus C]$ that contains a marked vertex and whose only neighbor in $C$ is the vertex $w$. Because $|C|$ is larger than the number of marked vertices, there exists a vertex in $C$ that is not necessary, let $w\in C$ be such a vertex. We remove from $X_{v}$ the vertex $w$ and every component of $G[X_{v}\setminus C]$ whose only neighbor in $C$ is $w$. All of the remaining vertices in $X_{v}$ are still connected to $C\setminus\{w\}$ and contain all of the marked vertices, so we get a connected induced proper subgraph of $G[X_{v}]$ that contains all of the marked vertices, which is a contradiction. ∎

Otherwise, we could remove $w$ from $X_{v}$ and contradict the minimality of $\{X_{v}\}_{v\in V(H)}$. ∎

Let $p=12$ and $t=2\binom{p}{2}+2=134$. Let $G$ be a graph with girth at least $p+1$, and let $\{X_{v}\}_{v\in V(K_{t,p})}$ be a minimal induced minor model of $K_{t,p}$ in $G$. We denote the branch sets corresponding to vertices of $K_{t,p}$ on the side with $t$ vertices by $A_{1},\ldots,A_{t}$ and on the other side by $B_{1},\ldots,B_{p}$. Note that $G$ is triangle-free.

First suppose that there are two branch sets $A_{i}$, $A_{j}$ of size $|A_{i}|,|A_{j}|\leq 2$. In this case, there must be a vertex $v\in A_{i}$ that is adjacent to at least $p/2$ different branch sets on the other side, and a vertex $u\in A_{j}$ that is adjacent to at least $p/4=3$ different branch sets on the other side that $v$ is also adjacent to. Fix three different branch sets $B_{a}$, $B_{b}$, $B_{c}$ that both $v$ and $u$ are adjacent to. Now, by selecting in each branch set $B_{a}$, $B_{b}$, $B_{c}$ a shortest path from a neighbor of $v$ to a neighbor of $u$, we obtain a theta from $u$ to $v$.

We may therefore assume that at least $t-1$ of the branch sets $A_{1},\ldots,A_{t}$ contain at least three vertices. By Lemma 4.1 and because $G$ has girth at least $p+1$, for all branch sets $A_{1},\ldots,A_{t}$ the induced subgraph $G[A_{i}]$ is a tree, and for all such sets with $|A_{i}|\geq 3$, the tree must have two non-adjacent leaves $v$ and $u$. By Lemma 4.2, both $v$ and $u$ have a private branch set on the other side, so we can label each branch set $A_{i}$ with $|A_{i}|\geq 3$ with an unordered pair $\{B_{j},B_{k}\}$ so that $B_{j}$ is private to $v$ and $B_{k}$ is private to $u$.

Now, because $t-1=2\binom{p}{2}+1$, there must exist three branch sets $A_{a}$, $A_{b}$, and $A_{c}$ that are labeled with the same pair $\{B_{j},B_{k}\}$. By contracting both $B_{j}$ and $B_{k}$ into a single vertex and taking the paths in $A_{a}$, $A_{b}$, and $A_{c}$ between the corresponding leaves, we obtain $K^{*}_{2,3}$ as an induced minor. By Lemma 2.3, $G$ must contain a theta since the theta is the only triangle-free 3PC. ∎

By Lemma 2.2 applied to $A=A_{i}$, $B=A_{j}$ for some $j\neq i$ and $X$, $Y$ and $Z$, we see that all $A_{i}$’s are of type path with respect to $X$, $Y$ and $Z$. It remains to prove that they all share a common center.

We denote by $\tau(A_{i})$ the sets of all elements $U\in\{X,Y,Z\}$ such that $A_{i}$ is centered at $U$. Note that for all $i\in\{1,\dots,k\}$, $\tau(A_{i})$ is nonempty. It is enough to prove that for all $i,j\in\{1,\dots,k\}$, either $\tau(A_{i})\subseteq\tau(A_{j})$ or $\tau(A_{j})\subseteq\tau(A_{i})$. Indeed, this implies that the sets $\tau(A_{i})$ are linearly ordered by the inclusion, so that $\cap_{i\in\{1,\dots,k\}}\tau(A_{i})$ is non-empty and contains the common center that we are looking for.

So suppose for a contradiction that $A=A_{i}$ and $B=A_{j}$ are such that $\tau(A_{i})$ and $\tau(A_{j})$ are inclusion-wise incomparable. So, up to symmetry, $A$ is centered at $X$ and not at $Y$ while $B$ is centered at $Y$ and not at $X$.

Since $A$ is centered at $X$, there exists $P=u\dots u^{\prime}$ in $A$ such that $u$ sees $Y$, $u^{\prime}$ sees $Z$, $P$ sees $X$, $P\setminus u$ is anticomplete to $Y$ and $P\setminus u^{\prime}$ is anticomplete to $Z$. Since $B$ is centered at $Y$, there exists $Q=v\dots v^{\prime}$ in $B$ such that $v$ sees $X$, $v^{\prime}$ sees $Z$, $Q$ sees $Y$, $Q\setminus v$ is anticomplete to $X$ and $Q\setminus v^{\prime}$ is anticomplete to $Z$.

Let $R=z\dots z^{\prime}$ be a shortest path in $Z$ such that $u^{\prime}z\in E(G)$ and $z^{\prime}v^{\prime}\in E(G)$. Let $S=y\dots y^{\prime}$ be a shortest path in $Y$ such that $y$ sees $Q$ and $y^{\prime}u\in E(G)$. Let $T=x\dots x^{\prime}$ be a shortest path in $X$ such that $x$ sees $P$ and $x^{\prime}v\in E(G)$. Observe that each of $P$, $Q$, $R$, $S$ and $T$ can be of length 0.

Let $a$ be the neighbor of $x$ in $P$ closest to $u$ along $P$. Let $a^{\prime}$ be the neighbor of $x$ in $P$ closest to $u^{\prime}$ along $P$. Let $b$ be the neighbor of $y$ in $Q$ closest to $v$ along $Q$. Let $b^{\prime}$ be the neighbor of $y$ in $Q$ closest to $v^{\prime}$ along $Q$. See Figure 8.

Suppose first that $a=a^{\prime}$. Observe that $a=a^{\prime}\neq u$ for otherwise $A$ would be centered at $Y$, contrary to our assumption. Hence, $ay\notin E(G)$. If $b=b^{\prime}$, then $P$, $Q$, $R$, $S$ and $T$ form a theta from $a$ to $b$, so $b\neq b^{\prime}$. If $bb^{\prime}\in E(G)$, then $P$, $Q$, $R$, $S$ and $T$ form a pyramid from $a$ to $ybb^{\prime}$. If $bb^{\prime}\notin E(G)$, then $P$, $vQb$, $b^{\prime}Qv^{\prime}$, $R$, $S$ and $T$ form a theta from $a$ to $y$ (because $ay\notin E(G)$ as already noted). Hence $a\neq a^{\prime}$, and symmetrically we can prove that $b\neq b^{\prime}$.

Suppose now $aa^{\prime}\in E(G)$. If $bb^{\prime}\in E(G)$, then $P$, $Q$, $R$, $S$ and $T$ form a prism from $xaa^{\prime}$ to $ybb^{\prime}$. If $bb^{\prime}\notin E(G)$, then $P$, $vQb$, $b^{\prime}Qv^{\prime}$, $R$, $S$ and $T$ form a pyramid from $y$ to $xaa^{\prime}$. Hence $aa^{\prime}\notin E(G)$, and symmetrically we can prove that $bb^{\prime}\notin E(G)$.

We are left with the case where $a\neq a^{\prime}$, $aa^{\prime}\notin E(G)$, $b\neq b^{\prime}$ and $bb^{\prime}\notin E(G)$. Then $uPa$, $a^{\prime}Pu^{\prime}$, $vQb$, $b^{\prime}Qv^{\prime}$, $R$, $S$ and $T$ form a theta from $x$ to $y$. ∎

By Lemma 5.1, $A$, $B$ and $C$ are of type path with respect to $X$, $Y$ and $Z$, centered at some $Y^{\prime}\in\{X,Y,Z\}$. By Lemma 5.1, $X$, $Y$ and $Z$ are of type path with respect to $A$, $B$ and $C$, centered at some $B^{\prime}\in\{A,B,C\}$. We let $X^{\prime}$, $Z^{\prime}$, $A^{\prime}$ and $C^{\prime}$ be such that $\{A^{\prime},B^{\prime},C^{\prime}\}=\{A,B,C\}$ and $\{X^{\prime},Y^{\prime},Z^{\prime}\}=\{X,Y,Z\}$.

So, $A^{\prime}$ contains some path that sees $X^{\prime}$, $Y^{\prime}$ and $Z^{\prime}$ as in the definition of type path centered at $Y^{\prime}$, but by the assumption about the minimality of $A$, $B$ or $C$, we see that this path is in fact $A^{\prime}$ itself. So $A^{\prime}$ is equal to exactly one of $A$, $B$ or $C$. The arguments works also with $B$ and $C$, so that $A^{\prime}=a\dots a^{\prime}$, $B^{\prime}=b\dots b^{\prime}$, $C^{\prime}=c\dots c^{\prime}$, each of $a$, $b$ and $c$ sees $X^{\prime}$, each of $a^{\prime}$, $b^{\prime}$ and $c^{\prime}$ sees $Z^{\prime}$, each of $A^{\prime}$, $B^{\prime}$ and $C^{\prime}$ sees $Y^{\prime}$, each of $A^{\prime}\setminus a$, $B^{\prime}\setminus b$ and $C^{\prime}\setminus c$ is anticomplete to $X^{\prime}$ and each of $A^{\prime}\setminus a^{\prime}$, $B^{\prime}\setminus b^{\prime}$ is and $C^{\prime}\setminus c^{\prime}$ is anticomplete to $Z^{\prime}$.

Also $X^{\prime}$ contains a path $P=p\dots p^{\prime}$ such that $p$ sees $A^{\prime}$, $p^{\prime}$ sees $C^{\prime}$, $P\setminus p$ is anticomplete to $A^{\prime}$, $P\setminus p^{\prime}$ is anticomplete to $C^{\prime}$ and $P$ sees $B^{\prime}$. Note that we cannot claim that $X^{\prime}=P$, since we made no assumption about the minimality of $X$. But since $A^{\prime}\setminus a$ is anticomplete to $X^{\prime}$ and $P\setminus p$ is anticomplete to $A^{\prime}$, the only possible edge between $P$ and $A^{\prime}$ is $pa$. Similarly, $p^{\prime}c$ is the only edge between $P$ and $C^{\prime}$. Moreover, $P$ sees $B^{\prime}$, and since $B\setminus b$ is anticomplete to $X^{\prime}$, we know that $b$ sees $P$ (and not only $X^{\prime}$).