For a family \(\mathcal F\) of graphs, a graph \(G\) is said to be \(\mathcal F\)-free if \(G\) contains no member of \(\mathcal F\) as an induced subgraph. We let \(\mathcal G_{3}(\mathcal F)\) be the family of \(3\)-connected \(\mathcal F\) -free graphs. Let \(P_{n}\) and \(C_{n}\) denote the path and the cycle of order \(n\), respectively. Let \(T_{0}\) be the tree of order nine obtained by joining a pendant edge to the central vertex of \(P_{7}\). Let \(T_{1}\) and \(T_{2}\) be the trees of order ten obtained from \(T_{0}\) by joining a new vertex to a vertex of \(P_{7}\) adjacent to an endvertex, and to a vertex of \(P_{7}\) adjacent to the central vertex, respectively. We show that \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{1}\})\) and \(\mathcal G_{3}(\{C_{3}, C_{4}, T_{2}\})\) are finite families.
By a graph, we mean a finite, simple, undirected graph. Let \(G\) be a graph. We let \(V(G)\) and \(E(G)\) denote the vertex set and the edge set of \(G\), respectively. For \(u \in V(G)\), we let \(N_{G}(u)\) and \(\deg_{G}(u)\) denote the neighborhood and the degree of \(u\) in \(G\), respectively; thus \(\deg_{G}(u)=|N_{G}(u)|\). We let \(\delta(G)\) and \(\Delta(G)\) denote the minimum degree and the maximum degree of \(G\), respectively. For \(U \subseteq V(G)\), we set \(N_{G}(U)=\bigcup_{u \in U} N_{G}(u)\), and let \(G[U]\) denote the subgraph of \(G\) induced by \(U\). For \(U, U^{\prime} \subseteq V(G)\) with \(U \cap U^{\prime}=\varnothing\), we let \(E_{G}(U, U^{\prime})\) be the set of edges of \(G\) joining a vertex in \(U\) and a vertex in \(U^{\prime}\). When \(G\) is connected, for \(u, v \in V(G)\), we let \({\rm dist}(u,v)\) denote the distance of \(u\) and \(v\) in \(G\), and let \({\rm diam}(G)\) denote the maximum of \({\rm dist}(u,v)\) as \(u\) and \(v\) range over \(V(G)\). We let \(C_{n}\) and \(K_{n}\) denote the cycle and the complete graph of order \(n\), respectively. We let \(K_{m_{1}, m_{2}}\) denote the complete bipartite graph with partite sets having cardinalities \(m_{1}\) and \(m_{2}\), respectively. For terms and symbols not defined here, we refer the reader to Diestel [2].
Let \(n \ge 5\) be an integer, and let \(I\), \(J\) be subsets of \(\{2,3, \cdots, n-1\}\) with \(J \subseteq \{3, \cdots, n-2\}\) and \(I \cap J=\varnothing\). We let \(S_{n}(I,J)\) denote the tree obtained from a path \(u_{1} u_{2} \cdots u_{n}\) of order \(n\) by adding vertices \(v_{i}\ (i \in I\cup J)\) and \(v_{i}^{\prime}\ (i \in J)\) and edges \(u_{i} v_{i}\ (i \in I\cup J)\) and \(v_{i} v_{i}^{\prime}\ (i \in J)\). Also we let \(S^{*}\) denote the tree obtained from a path \(u_{1} u_{2} \cdots u_{7}\) of order \(7\) by adding vertices \(v_{4}\), \(v_{4}^{\prime}\), \(v_{4}^{\prime \prime}\) and edges \(u_{4} v_{4}\), \(v_{4} v_{4}^{\prime}\), \(v_{4} v_{4}^{\prime \prime}\) (see Figure 1).
For two graphs \(G\) and \(H\), we say that \(G\) is \(H\)-free if \(G\) does not contain an induced copy of \(H\). For a family \(\mathcal F\) of connected graphs, a graph \(G\) is said to be \(\mathcal F\)-free if \(G\) is \(H\)-free for every \(H\in \mathcal F\). For an integer \(k \ge 2\) and a family \(\mathcal F\) of connected graphs, let \(\mathcal G_{k}(\mathcal F)\) denote the family of \(k\)-connected \(\mathcal{F}\)-free graphs. In this context, members of \(\mathcal{F}\) are often referred to as forbidden subgraphs.
Let \(k\ge 2\) be an integer. In this paper, we consider families \(\mathcal{F}\) of connected graphs such that \[\label{1.1} \mathcal{G}_{k}(\mathcal{F}) \text{ is a finite family.} \tag{1}\]
Note that if a family \(\mathcal{F}\) satisfies (1), then for any property \(P\) on graphs, although the proposition that all \(k\)-connected \(\mathcal{F}\)-free graphs satisfy \(P\) with finite exceptions holds, the proposition gives no information about \(P\). Thus it is important to identify families \(\mathcal{F}\) satisfying (1) in advance. With such a motivation, studies of \(\mathcal{F}\) satisfying (1) have been started by Fujisawa, Plummer and Saito in [5]. In particular, it is known that if a finite family \(\mathcal{F}\) of connected graphs satisfies (1), then \(\mathcal{F}\) contains a complete graph, a complete bipartite graph and a tree. Based on this result, families \(\mathcal{F}\) satisfying (1) which are written in the form \(\mathcal{F}=\{K_{n}, K_{m_{1}, m_{2}}, T\}\) where \(n\ge 3\), \(2\le m_{1}\le m_{2}\) and \(T\) is a tree, have intensively been studied. For \(k=2\), such families are completely characterized in [5]. For \(k=3\), such families are characterized except for the case where \(n=3\) and \(m_{1}=m_{2}=2\) (see the references in [4]). For other related results, we refer the reader to Buelban et al. [], Furuya and Okubo [6], Kotani [7], and Kotani and Nishiyama []. This paper is concerned with the case where \(n=3\) and \(m_{1}=m_{2}=2\).
The following conjecture is proposed in [4] (note that \(K_{3}=C_{3}\) and \(K_{2,2}=C_{4}\)).
Conjecture 1.1. Let \(T\) be a tree. Then \(\mathcal{G}_{3}(\{C_{3}, C_{4}, T\})\) is finite if and only if \(T\) is a subgraph of one of \(S_{9}(\{2\}, \varnothing)\), \(S_{9}(\{5\}, \varnothing)\), \(S_{9}(\varnothing, \{3\})\), \(S_{8}(\{2, 5\}, \varnothing)\), \(S_{8}(\{7\}, \{3\})\), \(S_{8}(\{4, 5, 6\},\\ \{3\})\), \(S_{8}(\{4\}, \{3, 6\})\), \(S_{7}(\{2\}, \{4\})\), \(S_{7}(\{3\}, \{4\})\), \(S_{7}(\{4\}, \{3, 5\})\), \(S^{*}\) and \(S_{6}(\varnothing, \{3, 4\})\).
The ‘only if’ part of the conjecture is proved in [4]. As for the ‘if’ part, it is
proved in [3, 4] that \(\mathcal{G}_{3}(\{C_{3}, C_{4},T\})\) is
finite if
\(T=S_{9}(\{2\}, \varnothing), S_{9}(\{5\},
\varnothing), S_{9}(\varnothing, \{3\}), S_{8}(\{2, 5\},
\varnothing)\) or \(S_{8}(\{7\},
\{3\})\). In this paper, we prove the following theorem.
Theorem 1.2. The families \(\mathcal{G}_{3}(\{C_{3}, C_{4}, S_{7}(\{2\}, \{4\})\})\) and \(\mathcal{G}_{3}(\{C_{3}, C_{4}, S_{7}(\{3\}, \{4\})\})\) are finite families.
Together with the results mentioned above, this reduces Conjecture 1.1 to the following conjecture.
Conjecture 1.3. Let \(T\) be a tree isomorphic to \(S_{8}(\{4, 5, 6\}, \{3\})\), \(S_{8}(\{4\}, \{3, 6\})\),
\(S_{7}(\{4\}, \{3, 5\})\), \(S^{*}\) or \(S_{6}(\varnothing, \{3, 4\})\). Then \(\mathcal{G}_{3}(\{C_{3}, C_{4}, T\})\) is a
finite family.
The following lemma is well-known (see [2, Proposition 1.3.3]).
Lemma 1.4. Let \(m\ge 2\) and \(d\ge 3\) be integers, and let \(G\) be a graph with \(\Delta(G) \le m\) and \({\rm diam}(G)\le d\). Then \(|V(G)|\le m^{d}\).
Having Lemma 1.4 in mind, we establish Theorem 1.2 by bounding the diameter and the maximum degree of \(\{C_{3}, C_{4}, T\}\)-free graphs for \(T=S_{7}(\{2\}, \{4\})\) and \(T=S_{7}(\{3\}, \{4\})\). Specifically, we prove the following three propositions.
Proposition 1.5. Let \(G\) be a \(3\)-connected \(\{C_{3}, C_{4}, T\}\)-free graph, where \(T=S_{7}(\{2\}, \{4\})\) or \(S_{7}(\{3\}, \{4\})\). Then \({\rm diam}(G)\le 24\).
Proposition 1.6. Let \(G\) be a \(3\)-connected \(\{C_{3}, C_{4}, S_{7}(\{2\}, \{4\})\}\)-free graph. Then \(\Delta(G)<3\cdot 10^{4}\).
Proposition 1.7. Let \(G\) be a \(3\)-connected \(\{C_{3}, C_{4}, S_{7}(\{3\}, \{4\})\}\)-free graph. Then \(\Delta(G)<4.1\cdot 10^{5}\).
We prove Proposition 1.5 in Sections 2 and 3, and prove Propositions 1.6 and 1.7 in Sections 4, 5 and 6. We here mention that unlike in [3] or [4], bounding the diameter of graphs in \(\mathcal{G}_{3} (\{C_{3}, C_{4}, S_{7}(\{2\}, \{4\})\}) \cup \mathcal{G}_{3} (\{C_{3}, C_{4}, S_{7}(\{3\}, \{4\})\})\) is nontrivial. We add that in Section 4, we use the fact that \(R(3,3)=6\) and \(R(3,4)=9\), where \(R(s,t)\) denotes the usual Ramsey number, i.e., the minimum positive integer \(R\) such that any graph of order at least \(R\) contains a complete subgraph of order \(s\) or an independent set of cardinality \(t\). We here state a corollary of a famous theorem of Turán [10], which appears as Theorem 7.1.1 in [2]. Let \(H\) be a graph, let \(k\) be the maximum cardinality of an independent set of \(H\), and write \(n=kq+r\), where \(q,r\) are integers with \(0 \leq r \leq k-1\). Turán’s theorem shows that \(|E(H)| \geq r|E(K_{q+1})|+(k-r)|E(K_q)|\). By calculations, we obtain \(2|E(H)| \geq |V(H)|((|V(H)|/k)-1)\); i.e., if \(H\) has average degree at most \(d\), then \(d \geq (|V(H)|/k)-1\). This shows that the following lemma holds (see also Nagayama [9]).
Lemma 1.8. Let \(H\) be a graph with average degree at most \(d\). Then \(H\) contains an independent set with cardinality greater than or equal to \(|V(H)|/(d+1)\).
Throughout the rest of this paper, for simplicity, we let \(S_{7}(\{2\}, \{4\})\) and \(S_{7}(\{3\}, \{4\})\) be denote by \(T_{1}\) and \(T_{2}\), respectively.
In this section and the following section, we let \(G\) denote a \(3\)-connected \(\{C_{3}, C_{4}\}\)-free graph with \({\rm diam} (G) \ge 25\). Let \(d={\rm diam} (G)\), take \(u, v \in V(G)\) with \({\rm dist} (u,v)=d\), and let \(P=u_{0} u_{1} \cdots u_{d}\) be a shortest \(u\)–\(v\) path. The first two lemmas follow immediately from the fact that \(G\) is \(\{C_{3}, C_{4}\}\)-free and \(P\) is a shortest \(u\)–\(v\) path (we will make use of Lemma 2.1 without referring to it explicitly).
Lemma 2.1. Let \(a \in N_{G}(V(P))-V(P)\). Then \(|N_{G}(a)\cap V(P)|=1\).
Lemma 2.2. Let \(0\le i,i^{\prime} \le d\), \(a_{i} \in N_{G}(u_{i})-V(P)\) and \(a_{i^{\prime}} \in N_{G}(u_{i^{\prime}})-V(P)\), and suppose that \(a_{i} a_{i^{\prime}}\in E(G)\). Then \(|i-i^{\prime}|=2\) or \(3\).
Lemma 2.3. Let \(0\le i,i^{\prime} \le d\), and let \(a \in N_{G}(u_{i})-V(P)\).
(i) Let \(i\ge i^{\prime}+3\), and suppose that \({\rm dist}(u_{i^{\prime}}, a)\le i-i^{\prime}-1\). Then for each \(y \in (N_{G}(a)-\{u_{i}\}) \cap N_{G}(V(P))\), we have \(y \in N_{G}(u_{i-3})\) or \(y \in N_{G}(u_{i-2})\).
(ii) Let \(i\le i^{\prime}-3\), and suppose that \({\rm dist}(u_{i^{\prime}}, a)\le i^{\prime}-i-1\). Then for each \(y \in (N_{G}(a)-\{u_{i}\}) \cap N_{G}(V(P))\), we have \(y \in N_{G}(u_{i+2})\) or \(y \in N_{G}(u_{i+3})\).
Proof. Assume that \(i\ge i^{\prime}+3\) and \({\rm dist}(u_{i^{\prime}}, a)\le i-i^{\prime}-1\). Let \(y \in (N_{G}(a)-\{u_{i}\}) \cap V(P)\), and write \(N_{G}(y) \cap V(P)=\{u_{j}\}\). By Lemma 2.2, \(j \in \{i-3, i-2, i+2, i+3\}\). If \(j\in \{i+2, i+3\}\), then we get \({\rm dist}(u_{i^{\prime}}, u_{j})\le {\rm dist}(u_{i^{\prime}}, a)+{\rm dist}(a, u_{j})\le (i-i^{\prime}-1)+2=(i+1)-i^{\prime}<j-i^{\prime}\) by assumption, which contradicts the fact that \({\rm dist}(u_{i^{\prime}}, u_{j})=j-i^{\prime}\). Thus \(j\in \{i-3, i-2\}\), which proves (i). By symmetry, (ii) is verified in a similar way. ◻
We now prove lemmas concerning the case where \(G\) is \(T_{1}\)-free.
Lemma 2.4. Suppose that \(G\) is \(T_{1}\)-free. Let \(6\le i\le d-3\), \(a_{i-3}\in N_{G}(u_{i-3})-V(P)\) and \(a_{i}\in N_{G}(u_{i})-V(P)\), and suppose that \(a_{i-3} a_{i}\in E(G)\). Then the following hold.
(i) We have \(|N_{G}(u_{i-2})-V(P)|=|N_{G}(a_{i})-\{u_{i}, a_{i-3}\}|=1\) and \(N_{G}(u_{i-2})-V(P)=N_{G}(a_{i})-\{u_{i}, a_{i-3}\}\).
(ii) We have \(|N_{G}(u_{i-1})-V(P)|=|N_{G}(a_{i-3})-\{u_{i-3}, a_{i}\}|=1\) and \(N_{G}(u_{i-1})-V(P)=N_{G}(a_{i-3})-\{u_{i-3}, a_{i}\}\).
Proof. Let \(x\) be an arbitrary vertex in \(N_{G}(u_{i-2})-V(P)\). Let \(a_{i+2} \in N_{G}(u_{i+2})-V(P)\). Since \(G\) is \(T_{1}\)-free, \(\{x, u_{i-2}, u_{i-1}, u_{i}, a_{i}, a_{i-3}, u_{i+1}, u_{i+2}, a_{i+2}, u_{i+3}\}\) does not induce a copy of \(T_{1}\). In view of Lemma 2.2, this implies \(\{x a_{i}, a_{i} a_{i+2}\} \cap E(G) \neq \varnothing\). Applying Lemma 2.3 (i) with \(i^{\prime}=i-3\) and \(y=a_{i+2}\), we also get \(a_{i+2} \notin N_{G}(a_{i})\). Hence \(x a_{i} \in E(G)\). Recall that \(G\) is \(\{C_{3}, C_{4}\}\)-free. Since \(x \in N_{G}(u_{i-2})-V(P)\) is arbitrary, it follows that \(N_{G}(u_{i-2})-V(P)=\{x\}\). Note that \(Q=u_{d} \cdots u_{i} a_{i} a_{i-3} u_{i-3} \cdots u_{0}\) is a shortest \(v\)–\(u\) path. Hence applying the above argument with \(P\), \(u_{i-3}\) and \(u_{i}\) replaced by \(Q\), \(u_{i}\) and \(u_{i-3}\), respectively, we obtain \(N_{G}(a_{i})-V(Q)=\{x\}\). Since \(N_{G}(a_{i})-V(Q)=N_{G}(a_{i})-\{u_{i}, a_{i-3}\}\), this proves (i). Applying (i) to \(u_{0} \cdots u_{i-3} a_{i-3} a_{i} u_{i} \cdots u_{d}\), we see that (ii) holds. ◻
Lemma 2.5. Suppose that \(G\) is \(T_{1}\)-free, let \(0\le i, i^{\prime}\le d\), and let \(a_{i} \in N_{G}(u_{i})-V(P)\).
(i) Let \(i^{\prime}+3 \le i\le d-5\), and suppose that \({\rm dist}(u_{i^{\prime}}, a_{i})\le i-i^{\prime}-1\). Then \(N_{G}(a_{i}) \subseteq N_{G}(V(P))\).
(ii) Let \(5\le i\le i^{\prime}-3\), and suppose that \({\rm dist}(u_{i^{\prime}}, a_{i})\le i^{\prime}-i-1\). Then \(N_{G}(a_{i}) \subseteq N_{G}(V(P))\).
Proof. Assume that \(i^{\prime}+3 \le i\le d-5\) and \({\rm dist}(u_{i^{\prime}}, a_{i})\le i-i^{\prime}-1\). Suppose that \(N_{G}(a_{i}) \nsubseteq N_{G}(V(P))\), and take \(b\in N_{G}(a_{i}) -N_{G}(V(P))\). Let \(a_{i+2}\in N_{G}(u_{i+2})-V(P)\). Applying Lemma 2.3 (i) with \(y=a_{i+2}\), we get \(a_{i+2} \notin N_{G}(a_{i})\). Since \[\{u_{i-3}, u_{i-2}, u_{i-1}, u_{i}, a_{i}, b, u_{i+1}, u_{i+2}, a_{i+2}, u_{i+3} \},\] does not induce a copy of \(T_{1}\), it follows that \(b a_{i+2}\in E(G)\). Let \(a_{i+4}\in N_{G}(u_{i+4})-V(P)\).
Since \[\{u_{i-1}, u_{i}, u_{i+1}, u_{i+2}, a_{i+2}, b, u_{i+3}, u_{i+4}, a_{i+4}, u_{i+5} \},\] does not induce \(T_{1}\), we see that \(\{b a_{i+4}, a_{i+2} a_{i+4}\} \cap E(G) \neq \varnothing\). Consequently \[\begin{aligned} {\rm dist}(u_{i^{\prime}}, u_{i+4}) &\le {\rm dist}(u_{i^{\prime}}, a_{i})+{\rm dist}(a_{i}, b)+{\rm dist}(b, a_{i+4})+{\rm dist}(a_{i+4}, u_{i+4})\\ &\le (i-i^{\prime}-1)+1+2+1=i-i^{\prime}+3, \end{aligned}\] a contradiction. This proves (i), and (ii) is verified in a similar way. ◻
We proceed to the case where \(G\) is \(T_{2}\)-free.
Lemma 2.6. Suppose that \(G\) is \(T_{2}\)-free. Let \(4\le i\le d-4\), and let \(a_{i}\in N_{G}(u_{i}) -V(P)\). Then \(N_{G}(a_{i}) \subseteq N_{G}(V(P))\).
Proof. Since \(d\ge 9\), we have \(i\ge 5\) or \(i\le d-5\). By symmetry, we may assume that \(i\ge 5\). Suppose that \(N_{G}(a_{i}) \nsubseteq N_{G}(V(P))\), and take \(b\in N_{G}(a_{i}) -N_{G}(V(P))\). For each \(j\in \{i-3, i-2, i-1, i+1, i+2\}\), let \(a_{j}\in N_{G}(u_{j}) -V(P)\). Since \[\{u_{i-3}, u_{i-2}, u_{i-1}, u_{i}, a_{i}, b, u_{i+1}, a_{i+1}, u_{i+2}, u_{i+3} \},\] does not induce \(T_{2}\), it follows from Lemma 2.2 that \(b a_{i+1}\in E(G)\). Since \(i+1\le d-3\), applying the same argument with \(i\) and \(i+1\) replaced by \(i+1\) and \(i+2\), respectively, we get \(b a_{i+2}\in E(G)\). Since \(i-2\ge 3\), we similarly get \(b a_{i-1}\in E(G)\), \(b a_{i-2}\in E(G)\), \(b a_{i-3}\in E(G)\). Consequently \(u_{i-3} a_{i-3} b a_{i+2} u_{i+2}\) is a \(u_{i-3}-u_{i+2}\) path of length four, a contradiction. ◻
The following lemma shows that the conclusion of Lemma 2.4 holds for \(T_{2}\)-free graphs as well.
Lemma 2.7. Suppose that \(G\) is \(T_{2}\)-free. Let \(7\le i\le d-4\), \(a_{i-3}\in N_{G}(u_{i-3}) -V(P)\) and \(a_{i}\in N_{G}(u_{i}) -V(P)\), and suppose that \(a_{i-3} a_{i}\in E(G)\). Then the following hold.
(i) We have \(|N_{G}(u_{i-2})-V(P)|=|N_{G}(a_{i})-\{u_{i}, a_{i-3}\}|=1\) and \(N_{G}(u_{i-2})-V(P)=N_{G}(a_{i})-\{u_{i}, a_{i-3}\}\).
(ii) We have \(|N_{G}(u_{i-1})-V(P)|=|N_{G}(a_{i-3})-\{u_{i-3}, a_{i}\}|=1\) and \(N_{G}(u_{i-1})-V(P)=N_{G}(a_{i-3})-\{u_{i-3}, a_{i}\}\).
Proof. Let \(x\in N_{G}(a_{i})-\{u_{i}, a_{i-3}\}\). By Lemma 2.6, \(x\in N_{G}(V(P))\). Applying Lemma 2.3 (i) with \(i^{\prime}=i-3\), we get \(x\in N_{G}(u_{i-3}) \cup N_{G}(u_{i-2})\). Since \(a_{i-3}\in N_{G}(u_{i-3}) \cap N_{G}(a_{i})\) and \(G\) is \(\{C_{3}, C_{4}\}\)-free, we have \(x\notin N_{G}(u_{i-3})\). Hence \(x\in N_{G}(u_{i-2})\). Since \(x\in N_{G}(a_{i})-\{u_{i}, a_{i-3}\}\) is arbitrary and \(G\) is \(\{C_{3}, C_{4}\}\)-free, it follows that \(N_{G}(a_{i})-\{u_{i}, a_{i-3}\}=\{x\}\). Applying the above argument with \(P\), \(u_{i-3}\) and \(u_{i}\) replaced by \(u_{d} \cdots u_{i} a_{i} a_{i-3} u_{i-3} \cdots u_{0}\), \(u_{i}\) and \(u_{i-3}\), respectively, we also obtain \(N_{G}(u_{i-2})-V(P)=\{x\}\). Thus (i) is proved. Applying (i) to \(u_{0} \cdots u_{i-3} a_{i-3} a_{i} u_{i} \cdots u_{d}\), we see that (ii) holds. ◻
In this section, we prove Proposition 1.5. Thus let \(T=T_{1}\) or \(T_{2}\), and let \(G\) be a \(3\)-connected \(\{C_{3}, C_{4}, T\}\)-free graph and, by way of contradiction, suppose that \(d={\rm diam} (G)\ge 25\). Let \(P=u_{0}\cdots u_{d}\) be as in Section 2. We derive a contradiction by proving several claims.
Case 1. Let \(9\le i\le d-5\) and, for \(j\in \{i-4, i-2, i\}\), let \(a_{j} \in N_{G}(u_{j})-V(P)\). Then \(a_{i-4} a_{i-2}\notin E(G)\) or \(a_{i-2} a_{i}\notin E(G)\).
Proof. Suppose that \(a_{i-4} a_{i-2}, a_{i-2} a_{i} \in E(G)\). Then \({\rm dist} (u_{i-4},a_{i})\le 3\). Take \(b_{i}\in N_{G}(a_{i})-\{u_{i}, a_{i-2}\}\). By Lemma 2.5 (i) or 2.6, \(b_{i}\in N_{G}(V(P))\). Hence by Lemma 2.3 (i), \(b_{i}\in N_{G}(u_{i-3})\cup N_{G}(u_{i-2})\). Since \(a_{i-2}\in N_{G}(u_{i-2})\cap N_{G}(a_{i})\) and \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(b_{i}\notin N_{G}(u_{i-2})\). Hence \(b_{i}\in N_{G}(u_{i-3})\). Now take \(b_{i-4}\in N_{G}(a_{i-4})-\{u_{i-4}, a_{i-2}\}\). It follows from Lemma 2.5 (ii) or 2.6 and Lemma 2.3 (ii) that \(b_{i-4}\in N_{G}(u_{i-1})\). Since \(b_{i}\in N_{G}(u_{i-3})\), \(a_{i}\in N_{G}(u_{i})\), \(b_{i} a_{i}\in E(G)\), \(b_{i-4}\in N_{G}(u_{i-1})\) and \(a_{i-2}\in N_{G}(u_{i-2})\), it follows from (ii) of Lemma 2.4 or 2.7 that \(b_{i} b_{i-4}\in E(G)\), \(N_{G}(u_{i-1})=\{u_{i-2}, u_{i}, b_{i-4}\}\) and \(N_{G}(b_{i})=\{u_{i-3}, a_{i}, b_{i-4}\}\), and it follows from (i) of Lemma 2.4 or 2.7 that \(N_{G}(u_{i-2})=\{u_{i-3}, u_{i-1}, a_{i-2}\}\) and \(N_{G}(a_{i})=\{u_{i}, a_{i-2}, b_{i}\}\) (see Figure 2).
Similarly, applying Lemma 2.4 or 2.7 with \(u_{i-3}\) and \(u_{i}\) replaced by \(u_{i-4}\) and \(u_{i-1}\), we also get \(N_{G}(a_{i-4})=\{u_{i-4}, a_{i-2}, b_{i-4}\}\), \(N_{G}(u_{i-3})=\{u_{i-4}, u_{i-2}, b_{i}\}\) and \(N_{G}(b_{i-4})=\{u_{i-1}, a_{i-4}, b_{i}\}\). Note that \(Q=u_{0}\cdots u_{i-3} b_{i} a_{i} u_{i} \cdots u_{d}\) is a shortest \(u\)–\(v\) path, and we have \(a_{i-4}\in N_{G}(u_{i-4})-V(Q)\), \(a_{i-2}\in N_{G}(a_{i})-V(Q)\) and \(a_{i-4} a_{i-2}\in E(G)\). Consequently, applying (i) of Lemma 2.4 or 2.7 with \(P\), \(u_{i-3}\) and \(u_{i}\) replaced by \(Q\), \(u_{i-4}\) and \(a_{i}\), we obtain \(N_{G}(a_{i-2})=\{u_{i-2}, a_{i-4}, a_{i}\}\). Therefore \(\{u_{i-4}, u_{i}\}\) separates \(\{u_{i-3}, u_{i-2}, u_{i-1}, a_{i-4}, a_{i-2}, a_{i},\\ b_{i-4}, b_{i} \}\) from the rest. This contradicts the assumption that \(G\) is \(3\)-connected, which completes the proof of Claim 1. ◻
We here prove two technical claims concerning the case where \(T=T_{1}\).
Claim 2. Let \(T=T_{1}\). Let \(4\le i\le d-2\). For \(j\in \{i-4, i-2, i, i+2\}\), let \(a_{j} \in N_ {G}(u_{j})-V(P)\), and suppose that \(a_{i-2} a_{i}\in E(G)\).
(i) Let \(7 \le i\le d-7\). Suppose that \(N_{G}(a_{i})\nsubseteq N_{G}(P)\), and let \(b\in N_{G}(a_{i})-N_{G}(P)\). Then \(b a_{i+2}\in E(G)\).
(ii) Let \(9 \le i\le d-5\). Suppose that \(N_{G}(a_{i-2})\nsubseteq N_{G}(P)\), and let \(b\in N_{G}(a_{i-2})-N_{G}(P)\). Then \(b a_{i-4}\in E(G)\).
Proof. Assume that \(7 \le i\le d-7\) and \(N_{G}(a_{i})\nsubseteq N_{G}(P)\), and let \(b\in N_{G}(a_{i})-V(P)\). Since \(\{u_{i-3}, u_{i-2}, u_{i-1}, u_{i}, a_{i}, b, u_{i+1}, u_{i+2}, a_{i+2}, u_{i+3}\}\) does not induce \(T_{1}\), \(\{a_{i} a_{i+2}, b a_{i+2}\} \cap E(G) \neq \varnothing\). By Claim 1, \(a_{i} a_{i+2}\notin E(G)\). Hence \(b a_{i+2}\in E(G)\). This proves (i), and (ii) is verified in a similar way. ◻
Claim 3. Let \(T=T_{1}\). Let \(12\le i\le d-10\), \(a_{i-2} \in N_ {G}(u_{i-2})-V(P)\), and \(a_{i} \in N_ {G}(u_{i})-V(P)\), and suppose that \(a_{i-2} a_{i}\in E(G)\). Then \(N_{G}(a_{i-2})\subseteq N_{G}(V(P))\) and \(N_{G}(a_{i})\subseteq N_{G}(V(P))\).
Proof. Suppose that \(N_{G}(a_{i})\nsubseteq N_{G}(V(P))\), and take \(b_{i} \in N_ {G}(a_{i})-N_{G}(V(P))\). For \(j\in \{i+2, i+3, i+4, i+5\}\), let \(a_{j} \in N_ {G}(u_{j})-V(P)\). By Claim 2 (i), \(b_{i} a_{i+2}\in E(G)\). Since \(\{u_{i-1}, u_{i}, u_{i+1}, u_{i+2}, a_{i+2}, b_{i}, u_{i+3}, u_{i+4}, a_{i+4}, u_{i+5}\}\) does not induce \(T_{1}\), \(\{a_{i+2} a_{i+4}, b_{i} a_{i+4}\} \cap E(G) \neq \varnothing\). If \(b_{i} a_{i+4} \in E(G)\), then \({\rm dist}(u_{i-2}, u_{i+4})\le 5\), a contradiction. Thus \(b_{i} a_{i+4}\notin E(G)\). Hence \(a_{i+2} a_{i+4}\in E(G)\), which implies \({\rm dist}(u_{i-2}, a_{i+4})\le 5\). Take \(b_{i+4}\in N_{G}(a_{i+4})-\{u_{i+4}, a_{i+2}\}\). By Lemma 2.5 (i), \(b_{i+4}\in N_{G}(V(P))\). Hence by Lemma 2.3 (i), \(b_{i+4}\in N_{G}(u_{i+1})\cup N_{G}(u_{i+2})\). Since \(a_{i+2}\in N_{G}(u_{i+2})\cap N_{G}(a_{i+4})\) and \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(b_{i+4}\notin N_{G}(u_{i+2})\). Consequently \(b_{i+4}\in N_{G}(u_{i+1})\). Applying Lemma 2.4 (ii) with \(u_{i-3} a_{i-3} a_{i} u\) replaced by \(u_{i+1} b_{i+4} a_{i+4} u_{i+4}\), we see that \(a_{i+3} b_{i+4}\in E(G)\) (see Figure 3).
Note that \(Q=u_{0} \cdots u_{i+1} b_{i+4} a_{i+4} u_{i+4} \cdots u_{d}\) is shortest \(u\)–\(v\) path. We have already shown that \(b_{i} a_{i+4}\notin E(G)\). If \(b_{i} b_{i+4}\in E(G)\), then we get a conradiction by applying Claim 1 with \(P\), \(u_{i-4}\), \(u_{i-2}\) and \(u_{i}\) replaced by \(Q\), \(u_{i-2}\), \(u_{i}\) and \(b_{i+4}\), respectively. Thus \(b_{i} b_{i+4}\notin E(G)\). Hence \(b_{i} \notin N_{G}(V(Q))\). Note that \(a_{i+3} \in N_{G}(b_{i+4})\). Applying Claim 2 (i) to \(Q\), we now see that \(b_{i} a_{i+3}\in E(G)\). We already know that \(b_{i+4}\in N_{G}(u_{i+1})-V(P)\), \(a_{i+3}\in N_{G}(u_{i+3})-V(P)\) and \(b_{i+4} a_{i+3}\in E(G)\). We have just shown that \(b_i a_{i+3} \in E(G)\). Since \(b_i \notin N_G(V(P))\) by the choice of \(b_i\), it follows that \(b_{i}\in N_{G}(a_{i+3})-N_{G}(V(P))\). Therefore we can apply Claim 2 (i) with \(a_{i-2}\), \(a_i\) and \(b\) replaced by \(b_{i+4}\), \(a_{i+3}\) and \(b_i\), respectively, to obtain \(b_i a_{i+5} \in E(G)\), which implies \({\rm dist}(u_{i-2}, u_{i+5})\le 5\), a contradiction. Thus \(N_{G}(a_{i})\subseteq N_{G}(V(P))\). By symmetry, we similarly obtain \(N_{G}(a_{i-2})\subseteq N_{G}(V(P))\). ◻
Claim 4. Let \(12\le i\le d-10\), and let \(a_{i-2} \in N_ {G}(u_{i-2})-V(P)\) and \(a_{i} \in N_ {G}(u_{i})-V(P)\). Then \(a_{i-2} a_{i} \notin E(G)\).
Proof. Suppose that \(a_{i-2} a_{i} \in E(G)\). Take \(b_{i}\in N_{G}(a_{i})-\{u_{i}, a_{i-2}\}\). By Claim 3 or Lemma 2.6, \(b_{i}\in N_{G}(V(P))\). Hence \(b_{i}\in N_{G}(\{u_{i-3}, u_{i-2}, u_{i+2}, u_{i+3}\})\) by Lemma 2.2. If \(b_{i}\in N_{G}(u_{i+3})\), we get a contradiction by applying Lemma 2.3 (ii) with \(i^{\prime}=i+3\). Thus \(b_{i}\notin N_{G}(u_{i+3})\). By Claim 2 \(b_{i}\notin N_{G}(u_{i+2})\). Since \(a_{i-2}\in N_{G}(u_{i-2})\cap N_{G}(a_{i})\) and \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(b_{i}\notin N_{G}(u_{i-2})\). Consequently \(b_{i}\in N_{G}(u_{i-3})\). Let \(a_{i-1} \in N_ {G}(u_{i-1})-V(P)\). By (ii) of Lemma 2.4 or 2.7, \(a_{i-1} b_{i} \in E(G)\). Now take \(b_{i-2}\in N_{G}(a_{i-2})-\{u_{i-2}, a_{i}\}\). It follows from Claim 3 or Lemma 2.6, Lemma 2.2, Lemma 2.3 (i) and Claim 2 that \(b_{i-2}\in N_{G}(u_{i+1})\). Hence by (i) of Lemma 2.4 or 2.7, \(a_{i-1} b_{i-2} \in E(G)\). Therefore \(b_{i} \in N_ {G}(u_{i-3})-V(P)\), \(a_{i-1} \in N_ {G}(u_{i-1})-V(P)\), \(b_{i-2} \in N_ {G}(u_{i+1})-V(P)\) and \(b_{i} a_{i-1}, a_{i-1} b_{i-2} \in E(G)\), which contradicts Claim 1, completing the proof of the claim. ◻
Claim 5.Let \(12\le i\le d-10\), and let \(a_{i-3} \in N_ {G}(u_{i-3})-V(P)\) and \(a_{i} \in N_ {G}(u_{i})-V(P)\). Then \(a_{i-3} a_{i} \notin E(G)\).
Proof. Suppose that \(a_{i-3} a_{i} \in E(G)\). Let \(a_{i-2} \in N_ {G}(u_{i-2})-V(P)\). By (i) of Lemma 2.4 or 2.7, we get \(a_{i-2} a_{i} \in E(G)\), which contradicts Claim 4. ◻
We can now complete the proof of Proposition 1.5. Let \(a_{12} \in N_ {G}(u_{12})-V(P)\). Take \(b, b^{\prime}\in N_{G}(a_{12})-\{u_{12}\}\) with \(b \neq b^{\prime}\). By Claim 4, \(b, b^{\prime}\notin N_{G}(\{u_{10}, u_{14}\})\). By Claim 5, \(b, b^{\prime}\notin N_{G}(\{u_{9}, u_{15}\})\). Hence \(b, b^{\prime}\notin N_{G}(V(P))\) by Lemma 2.2. If \(T=T_{2}\), this contradicts Lemma 2.6. Thus \(T=T_{1}\). Let \(a_{10} \in N_ {G}(u_{10})-V(P)\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we have \(a_{10} b \notin E(G)\) or \(a_{10} b^{\prime} \notin E(G)\). We may assume that \(a_{10} b \notin E(G)\). By Claim 4, \(a_{10} a_{12} \notin E(G)\). Therefore \(\{u_{9}, u_{10}, a_{10}, u_{11}, u_{12}, a_{12}, b, u_{13}, u_{14}, u_{15}\}\) induces a copy of \(T_{1}\), which is a contradiction.
This completes the proof of Proposition 1.5.
Throughout the rest of this paper, we fix a \(3\)-connected \(\{C_{3}, C_{4}\}\)-free graph \(G\) and, for \(u \in V(G)\) and \(U \subseteq V(G)\), we write \(N(u)\) and \(N(U)\) for \(N_{G}(u)\) and \(N_{G}(U)\).
In this section and the following section, we study relation between induced paths joining two given vertices and the existence of an induced tree. For an integer \(k\ge 4\) and two nonadjacent vertices \(v\), \(w\) of \(G\), we let \[\begin{aligned} &M_{k}^{w}(v)\\&=\{x\in N(v)| \text{there exists an induced} \ v{\text{-}}w \ {\text {path}} \ P \ {\text {of order}} \ k \ {\text {such that}} \ N_{P}(v)=\{x\}\}. \end{aligned}\]
In the remainder of this section and the following section, we let \(v, w\) be nonadjacent vertices of \(G\). In this section, we deal with the case where \(M_{4}^{w}(v)\) is large. We first consider \(T_{1}\).
Lemma 4.1. Suppose that \(|M_{4}^{w}(v)|\ge 16\). Then \(G\) contains an induced copy of \(T_{1}\).
Proof. Take \(a_{1},\cdots, a_{16}\in M_{4}^{w}(v)\). For each \(i\in \{1, \cdots, 16\}\), let \(v a_{i} b_{i} w\) be an induced \(v\)–\(w\) path. Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(\{a_{i}, b_{i}\} \cap \{a_{j}, b_{j}\}=\varnothing\) for any \(i,j\) with \(i\neq j\), and \[\label{eq4.1} E(G[\{v, w\} \cup \{a_{i}, b_{i} | 1\le i \le 16\}])= \{v a_{i}, a_{i} b_{i}, b_{i} w | 1\le i \le 16\}. \tag{2}\]
For each \(i\in \{1, \cdots, 16\}\), take \(x_{i}\in N(a_{i})-\{v, b_{i}\}\). By (2), \(\{x_{i}| 1\le i \le 16\} \cap (\{v, w\}\cup \{a_{i}, b_{i}| 1\le i \le 16\})=\varnothing\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(x_{1},\cdots, x_{16}\) are distinct, \[\label{eq4.2} \text{$x_{i} a_{j} \notin E(G)$ for any $i,j\in \{1,\cdots, 16\}$ with $i\neq j$,} \tag{3}\] and \[\label{eq4.3} \text{$x_{i} v, x_{i} w, x_{i} b_{i} \notin E(G)$ for every $i\in \{1,\cdots, 16\}$.} \tag{4}\]
Now let \(D\) be the digraph on \(\{1,\cdots, 16\}\) obtained by joining \(i\) to \(j\) \((i\neq j)\) if and only if \(x_{i} b_{j} \in E(G)\), and let \(H\) be the (simple) graph obtain by ignoring the direction of the edges of \(D\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, each \(i\in \{1,\cdots, 16\}\) has outdegree at most one in \(D\). Hence \(|E(H)|\le |V(H)|\), which means that the average degree of \(H\) is at most two. In view of Lemma 1.8, we may assume that \(\{1,\cdots, 6\}\) is independent in \(H\). Then by (3) and (4), \[\label{eq4.4} E_{G}(\{x_{i}| 1\le i\le16\}, \{v, w\} \cup \{a_{i}| 1\le i\le16\} \cup \{b_{i}| 1\le i\le6\})=\{x_{i} a_{i}| 1\le i\le6\}. \tag{5}\]
Note that \(R(3,3)=6\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we may assume that \[\label{eq4.5} \{x_{1}, x_{2}, x_{3}\} \text{ is independent}. \tag{6}\]
Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we can take \(z_{1}\in N(x_{1})-\{a_{1}\}\) so that \(z_{1} w\notin E(G)\). By (5) and (6), \(z_{1} \notin \{w,v, x_{1}, x_{2}, x_{3}\} \cup \{a_{i}| 1\le i\le16\} \cup \{b_{i}| 1\le i\le6\}\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we have \(z_{1} a_{2}\notin E(G)\) or \(z_{1} a_{3}\notin E(G)\). We may assume that \(z_{1} a_{2}\notin E(G)\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, it follows that \[\label{eq4.6} z_{1} v, z_{1} w, z_{1} a_{1}, z_{1} a_{2}, z_{1} b_{1} \notin E(G). \tag{7}\]
Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(|N_{G}(z_{1})\cap \{b_{4}, b_{5}, b_{6}\}|\le 1\) and \(|N_{G}(z_{1})\cap \{a_{7}, a_{8}\}|\le 1\). We may assume that \(z_{1} b_{4}, z_{1} b_{5}, z_{1} a_{7} \notin E(G)\). Now if \(z_{1} x_{2} \in E(G)\), then it follows from (2), (5), (6) and (7) that \(\{x_{2} , z_{1}, x_{1}, a_{1}, v, a_{7}, b_{1}, w, b_{4}, b_{5}\}\) induces a copy of \(T_{1}\); if \(z_{1} x_{2}\notin E(G)\), then it follows from (2), (5), (6) and (7) that \(\{x_{2} , a_{2}, v, a_{1}, x_{1}, z_{1}, b_{1}, w, b_{4}, b_{5}\}\) induces a copy of \(T_{1}\) (see Figure 4). This completes the proof of Lemma 4.1.
Next we consider \(T_{2}\).
Lemma 4.2. Suppose that \(|M_{4}^{w}(v)|\ge 41\). Then \(G\) contains an induced copy of \(T_{2}\).
Proof. Take \(a_{1},\cdots, a_{41}\in M_{4}^{w}(v)\). For each \(i\in \{1, \cdots, 41\}\), let \(v a_{i} b_{i} w\) be an induced \(v\)–\(w\) path. Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(\{a_{i}, b_{i}\} \cap \{a_{j}, b_{j}\}=\varnothing\) for any \(i,j\) with \(i\neq j\), and \[\label{eq4.7} E(G[\{v, w\} \cup \{a_{i}, b_{i} | 1\le i \le 41\}])= \{v a_{i}, a_{i} b_{i}, b_{i} w | 1\le i \le 41\}. \tag{8}\]
For each \(i\in \{1, \cdots, 41\}\), take \(x_{i}\in N(a_{i})-\{v, b_{i}\}\) and \(y_{i}\in N(b_{i})-\{w, a_{i}\}\). By (2), \(\{x_{i}, y_{i}| 1\le i \le 41\} \cap (\{v, w\}\cup \{a_{i}, b_{i}| 1\le i \le 41\})=\varnothing\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(x_{i}\neq y_{i}\) for each \(i\), \(x_{1},\cdots, x_{41}\) are distinct, \(y_{1},\cdots, y_{41}\) are distinct, \[\label{eq4.8} \text{$x_{i} a_{j}, y_{i} b_{j} \notin E(G)$ for any $i,j\in \{1,\cdots, 41\}$ with $i\neq j$,} \tag{9}\] and \[\label{eq4.9} \text{$x_{i} v, y_{i} v, x_{i} b_{i}, y_{i} a_{i}, x_{i} y_{i} \notin E(G)$ for every $i\in \{1,\cdots, 41\}$.} \tag{10}\]
Now let \(D\) be the digraph on \(\{1,\cdots, 41\}\) obtained by joining \(i\) to \(j\) \((i\neq j)\) if and only if we have \(x_{i} b_{j} \in E(G)\) or \(y_{i} a_{j} \in E(G)\), and let \(H\) be the (simple) graph obtained by ignoring the direction of the edges of \(D\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, each \(i\in \{1,\cdots, 41\}\) has outdegree at most two in \(D\), which means that the average degree of \(H\) is at most four. In view of Lemma 1.8, we may assume that \(\{1,\cdots, 9\}\) is independent in \(H\). Then \(\{x_{i}| 1\le i\le 9\} \cap \{y_{i}| 1\le i\le 9\}=\varnothing\) and, by (9) and (10), \[\label{eq4.10} E_{G}(\{x_{i}, y_{i}| 1\le i\le 9\}, \{v\} \cup \{a_{i}, b_{i}| 1\le i\le 9\}) = \{x_{i} a_{i}, y_{i} b_{i}| 1\le i\le 9\}. \tag{11}\]
Note that \(R(3,4)=9\). Since \(G\) is \(C_{3}\)-free, we may assume that \(\{y_{1}, y_{2}, y_{3}, y_{4}\}\) is independent. Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, there exist \(i,j\in \{1,2,3,4\}\) with \(i\neq j\) such that \(x_{i} y_{j}\notin E(G)\). We may assume that \(x_{1} y_{2}\notin E(G)\). We now see from (8), (10) and (11) that \(\{y_{1}, b_{1}, a_{1}, x_{1}, v, a_{3}, b_{3}, a_{2}, b_{2}, y_{2}\}\) induces a copy of \(T_{2}\), as desired (see Figure 5). ◻
We continue with the notation of the preceding section. In this section, we consider the case where \(|M_{5}^{w}(v)|\) is large.
Lemma 5.1. Suppose that \(|M_{4}^{w}(v) \cup M_{5}^{w}(v)|\ge 511\). Then \(G\) contains an induced copy of \(T_{1}\).
Proof. In view of Lemma 4.1, we may assume that \(|M_{4}^{w}(v) |\le 15\). Then \(|M_{5}^{w}(v) – M_{4}^{w}(v)|\ge 496\). Take \(a_{1},\cdots, a_{496}\in M_{5}^{w}(v) – M_{4}^{w}(v)\). For each \(i\in \{1,\cdots, 496\}\), let \(v a_{i} b_{i} c_{i} w\) be an induced \(v\)–\(w\) path. If there exists \(c\in \{c_{1},\cdots, c_{496}\}\) such that \(| \{i\in \{1,\cdots, 496\}|c_{i}=c\}|\ge 16\), then \(|M_{4}^{c}(v) |\ge 16\), and hence the desired conclusion follows from Lemma 4.1. Thus we may assume that \(| \{i\in \{1,\cdots, 496\}|c_{i}=c\}|\le 15\) for each \(c\in \{c_{1},\cdots, c_{496}\}\). Then \(| \{c_{1},\cdots, c_{496}\}|\ge \lceil 496/15\rceil =34\). We may assume that \(c_{1},\cdots, c_{34}\) are distinct. Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we see that \(\{a_{i}, b_{i}, c_{i}\} \cap \{a_{j}, b_{j}, c_{j}\}=\varnothing\) for any \(i,j\in \{1,\cdots, 34\}\) with \(i\neq j\). Since \(a_{1},\cdots, a_{34}\notin M_{4}^{w}(v)\), \(a_{i} c_{j} \notin E(G)\) for any \(i,j\in \{1,\cdots, 34\}\) with \(i\neq j\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, it follows that \[\begin{aligned} \label{eq5.1} E(G[\{v, w\} \cup &\{a_{i}, b_{i}, c_{i}| 1\le i \le 34\}])- \{v a_{i}, a_{i} b_{i}, b_{i} c_{i}, c_{i} w | 1\le i \le 34\}\notag\\ &=E(G[\{b_{i}| 1\le i \le 34\}]). \end{aligned} \tag{12}\]
Since \(b_{1} w\notin E(G)\) by (12), we have \(N(b_{1}) \cap \{b_{i}| 2\le i \le 34\}\subseteq M_{4}^{w}(b_{1})\). Thus by Lemma 4.1, we may assume that \(|N(b_{1}) \cap \{b_{i}| 2\le i \le 34\}|\le 15\). We assume that \[\label{eq5.2} b_{1} b_{i}\notin E(G) \text{ for every } i\in \{2,\cdots, 19\}. \tag{13}\]
Take \(y_{1} \in N(b_{1}) – \{a_{1}, c_{1}\}\). By (12) and (13), \(y_{1} \notin \{v, w\}\cup \{a_{i}, b_{i}, c_{i}| 1\le i\le 19\}\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \[\label{eq5.3} y_{1} v, y_{1} w, y_{1} a_{1}, y_{1} c_{1} \notin E(G). \tag{14}\]
Since \(y_{1} w\notin E(G)\) by (14), we have \(b_{1} \in M_{4}^{w}(y_{1})\) and \(N(y_{1}) \cap \{b_{i}| 2\le i \le 19\} \subseteq M_{4}^{w}(y_{1})\). Thus by Lemma 4.1, we may assume that \(|N(y_{1}) \cap \{b_{i}| 2\le i \le 19\}|\le 14\). We may assume that \[\label{eq5.4} y_{1} b_{i}\notin E(G) \text{ for every } i\in \{2,\cdots, 5\}. \tag{15}\]
Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \(|N(y_{1}) \cap \{a_{2}, \cdots, a_{5}\}|\le 1\). We may assume that \(y_{1} a_{2}, y_{1} a_{3}, y_{1} a_{4} \notin E(G)\). Since \(G\) is \(C_{3}\)-free, some two of \(b_{2}, b_{3}\) and \(b_{4}\), say \(b_{2}\) and \(b_{3}\), are nonadjacent. Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we have \(y_{1} c_{2}\notin E(G)\) or \(y_{1} c_{3}\notin E(G)\). We may assume that \(y_{1} c_{2}\notin E(G)\). It now follows from (12) through (15) that \(\{c_{1}, b_{1}, y_{1}, a_{1}, v, a_{3}, b_{3}, a_{2}, b_{2}, c_{2}\}\) induces a copy of \(T_{1}\), as desired. ◻
Lemma 5.2. Suppose that \(|M_{4}^{w}(v) \cup M_{5}^{w}(v)|\ge 3361\). Then \(G\) contains an induced copy of \(T_{2}\).
Proof. By Lemma 4.2, we may assume that \(|M_{5}^{w}(v)-M_{4}^{w}(v)|\ge 3361-40=3321\). Take \(a_{1},\cdots, a_{3321}\in M_{5}^{w}(v) – M_{4}^{w}(v)\). For each \(i\in \{1,\cdots, 3321\}\), let \(v a_{i} b_{i} c_{i} w\) be an induced \(v\)–\(w\) path. By Lemma 4.2, we may assume that \(|\{c_{1},\cdots, c_{3321}\}|\ge \lceil3321/40\rceil=84\). We may assume that \(c_{1},\cdots, c_{84}\) are distinct. As in the proof of Lemma 5.1, we see that \(\{a_{i}, b_{i}, c_{i}\} \cap \{a_{j}, b_{j}, c_{j}\}=\varnothing\) for any \(i,j\in \{1,\cdots, 84\}\) with \(i\neq j\), and \[\begin{aligned} \label{eq5.5} E(G[\{v, w\} \cup &\{a_{i}, b_{i}, c_{i}| 1\le i \le 84\}])- \{v a_{i}, a_{i} b_{i}, b_{i} c_{i}, c_{i} w | 1\le i \le 84\}\notag\\ &=E(G[\{b_{i}| 1\le i \le 84\}]). \end{aligned} \tag{16}\]
Take \(x_{1} \in N(a_{1}) – \{v, b_{1}\}\). By (16), \(x_{1} \notin \{v, w\}\cup \{a_{i}, b_{i}, c_{i}| 1\le i\le 84\}\). Since \(a_{1}\notin M_{4}^{w}(v)\), \[\begin{aligned} \label{eq5.6} x_{1} w\notin E(G). \end{aligned} \tag{17}\]
Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, \[\label{eq5.7} x_{1} a_{i}\notin E(G) \text{ for every } i\in \{2,\cdots, 84\} \text{ and } x_{1} v, x_{1} b_{1}, x_{1} c_{1}\notin E(G). \tag{18}\]
We have \(N(b_{1}) \cap \{b_{2},\cdots, b_{84}\} \subseteq M_{4}^{w}(b_{1})\) by (16), and \(N(x_{1}) \cap \{b_{2},\cdots, b_{84}\} \subseteq M_{4}^{w}(x_{1})\) by (17). By Lemma 4.2, we may assume that \(b_{1} b_{i}, x_{i} b_{i}\notin E(G)\) for every \(i\in \{2, 3, 4\}\). Since \(G\) is \(\{C_{3}, C_{4}\}\)-free, we may assume that \(b_{2} b_{3}\notin E(G)\) and that \(x_{1} c_{2}\notin E(G)\). It now follows from (16) and (18) that \(\{c_{1}, b_{1}, a_{1}, x_{1}, v, a_{3}, b_{3}, a_{2}, b_{2}, c_{2}\}\) induces a copy of \(T_{2}\), as desired. ◻
In this section, we prove Propositions 1.6 and 1.7.
Recall that \(G\) denotes a \(3\)-connected \(\{C_{3}, C_{4}\}\)-free graph. In this section, we fix a vertex \(w\in V(G)\) with \(\deg_{G}(w)=\Delta(G)\).
For a vertex \(u\in V(G)\) and a nonnegative integer \(d\), let \(N_{d}(u)\) be the set of vertices of \(G\) such that \({\rm dist}(u,v)=d\), and let \(N_{\le d}(u)=\bigcup_{0\le i\le d} N_{i}(u)\) and \(N_{\ge d}(u)=\bigcup_{i\ge d} N_{i}(u)\); thus \(N_{0}(u)=\{u\}\) and \(N_{1}(u)=N(u)\). Clearly \(N(w)\) is independent, \(|N(x)\cap N_{2}(w)|\ge 2\) for every \(x\in N(w)\) and, since \(|N(y)\cap N(w)|\le 1\) for every \(y\in N_{\ge 2}(w)\), we have \(\delta(G[N_{\ge 2}(w)])\ge 2\). As in [4], for \(U\subseteq V(G)\), we let \(L(U)\) denote the set of those vertices \(v\in N_{2}(w) \cup N_{3}(w)\) for which there exists a \(v\)–\(w\) path of order four avoiding \(U\). The following three lemmas hold (see [3, Section 5]).
Lemma 6.1. Let \(X\subseteq N_{\ge 2}(w)\), and set \(Y_{1}=(X\cup N(X)) \cap N_{2}(w)\), \(Y_{2}=N(Y_{1})\cap N(w), Z_{1}= N(X)\cap L(X), Z_{2}=(X\cup N(X\cup Z_{1}))\cap N_{2}(w)\) and \(Z_{3}=N(Z_{2})\cap N(w)\). Then the following hold.
(i) If \(a\in N(w)-Y_{2}\), then \(E_{G}(X,N_{\le 1}(a))=\varnothing\).
(ii) If \(a\in N(w)-Z_{3}\), then \(E_{G}(X,N_{\le 2}(a)-Z_{3})=\varnothing\).
Lemma 6.2. Let \(X\subseteq N_{\ge 2}(w)\). Then \(N(X) \cap N_{2}(w)\subseteq \bigcup_{u \in X} M_{4}^{w}(u)\) and \(N(X)\cap L(X) \subseteq \bigcup_{u\in X} M_{5}^{w}(u)\).
Lemma 6.3. Let \(X\subseteq N_{\ge 2}(w)\), and let \(Y_{1}, Y_{2},Z_{1}, Z_{2}, Z_{3}\) be as in Lemma 6.1. Then
(i) \(|Y_{2}|\le |Y_{1}|\le |X-N(X)|+\sum_{u\in X}|M_{4}^{w}(u)|\),
(ii) \(|Z_{1}|\le \sum_{u\in X}|M_{5}^{w}(u)|\), and
(iii) \(|Z_{3}|\le |Z_{2}|\le |X-N(X\cup Z_{1})|+\sum_{u\in X\cup Z_{1}} |M_{4}^{w}(u)|\).
Proof of Proposition 1.6. By way of contradiction, suppose that \(G\) is \(T_{1}\)-free and \(\Delta(G)\ge 3\cdot 10^{4}\). By Lemmas 4.1 and 5., \[\label{eq6.1} |M_{4}^{w}(u)|\le 15\text{ and }|M_{5}^{w}(u)|\le |M_{4}^{w}(u) \cup M_{5}^{w}(u)|\le 510 \text{ for every } u\in N_{\ge 2}(w). \tag{19}\]
We seek for a contradiction. Let \(a_{1}\in N(w)\). Take \(a_{2}\in N(a_{1})\cap N_{\ge 2}(w)\) and \(a_{3}, a_{3}^{\prime}\in N(a_{2})\cap N_{\ge 2}(w)\) with \(a_{3}\neq a_{3}^{\prime}\). Set \(X=\{a_{2}, a_{3}, a_{3}^{\prime}\}\). Then \(E(G[X\cup \{a_{1}\}])=\{a_{3} a_{2}, a_{3}^{\prime} a_{2}, a_{2} a_{1}\}\). Let \(Z_{1}, Z_{3}\) be as in Lemma 6.1. We have \(X-N(X\cup Z_{1})=X-N(X)=\varnothing\). By Lemma 6.3 (ii), (iii) and (19), \(|Z_{1}|\le 3\cdot 510<1600\) and \(|Z_{3}|< 1603\cdot 15<3\cdot 10^{4} \le |N(w)|\). Let \(b_{1}\in N(w)-Z_{3}\), and take \(b_{2}\in N(b_{1})\cap N_{\ge 2}(w)\). Since \(\delta(G[N_{\ge 2}(w)])\ge 2\), we can take \(b_{3}\in N(b_{2})\cap N_{\ge 2}(w)\) so that \(a_{1} b_{3}\notin E(G)\) (see Figure 6). Then \(E(G[\{a_{1}, w, b_{1}, b_{2}, b_{3}\}])=\{a_{1} w, w b_{1}, b_{1} b_{2}, b_{2} b_{3}\}\). Since \(E_{G}(X, \{w, b_{1}, b_{2}, b_{3}\})=\varnothing\) by Lemma 6.1 (ii), it follows that \[E(G[X\cup \{a_{1}, w, b_{1}, b_{2}, b_{3}\}])=\{a_{3} a_{2}, a_{3}^{\prime} a_{2}, a_{2} a_{1}, a_{1} w, w b_{1}, b_{1} b_{2}, b_{2} b_{3}\}.\]
Let now \(X^{\prime}=X\cup \{b_{2}, b_{3}\}\). We have \(X^{\prime}-N(X^{\prime})=\varnothing\). Let \(Y_{2}\) be as in Lemma 6.1 with \(X\) replaced by \(X^{\prime}\). By Lemma 6.3 (i) and (19), \(|Y_{2}|\le 5\cdot 15<|N(w)|\). Let \(c_{1}\in N(w)-Y_{2}\), and take \(c_{2}\in N(c_{1})\cap N_{\ge 2}(w)\). Then \(E(G[\{a_{1}, b_{1}, w, c_{1}, c_{2}\}])=\{a_{1} w, b_{1} w, w c_{1}, c_{1} c_{2}\}\). Since \(E_{G}(X^{\prime}, \{w, c_{1}, c_{2}\})=\varnothing\) by Lemma 6.1 (i), we therefore see that \(X\cup \{a_{1}, w, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}\}\) induces a copy of \(T_{1}\). This contradicts the assumption that \(G\) is \(T_{1}\)-free, and completes the proof of Proposition 1.6. ◻
Proof of Proposition 1.7. Suppose that \(G\) is \(T_{2}\)-free and \(\Delta(G)\ge 4.1\cdot 10^{5}\). By Lemmas 4.2 and 5.2, \[\label{eq6.2} |M_{4}^{w}(u)|\le 40\text{ and }|M_{5}^{w}(u)|\le |M_{4}^{w}(u) \cup M_{5}^{w}(u)|\le 3360 \text{ for every } u\in N_{\ge 2}(w). \tag{20}\]
Let \(a_{1}\in N(w)\). Take \(a_{2}, a_{2}^{\prime}\in N(a_{1})\cap N_{\ge 2}(w)\) with \(a_{2}\neq a_{2}^{\prime}\), and take \(a_{3}\in N(a_{2})\cap N_{\ge 2}(w)\). Set \(X=\{a_{2}, a_{2}^{\prime}, a_{3}\}\). Then \(E(G[X\cup \{a_{1}\}])=\{a_{3} a_{2}, a_{2} a_{1}, a_{2}^{\prime} a_{1}\}\). Let \(Z_{1}, Z_{3}\) be as in Lemma 6.1. We have \(X-N(X\cup Z_{1})\subseteq X-N(X)=\{a_{2}^{\prime}\}\). By Lemma 6.3 (ii), (iii) and (20), \(|Z_{1}|\le 3\cdot 3360<10100\) and \(|Z_{3}|< 1+10103\cdot 40<4.1\cdot 10^{5} \le |N(w)|\). Let \(b_{1}\in N(w)-Z_{3}\), take \(b_{2}\in N(b_{1})\cap N_{\ge 2}(w)\), and take \(b_{3}\in N(b_{2})\cap N_{\ge 2}(w)\) with \(a_{1} b_{3}\notin E(G)\) (see Figure 7). Then \(E(G[\{a_{1}, w, b_{1}, b_{2}, b_{3}\}])=\{a_{1} w, w b_{1}, b_{1} b_{2}, b_{2} b_{3}\}\). Since \(E_{G}(X, \{w, b_{1}, b_{2}, b_{3}\})=\varnothing\) by Lemma 6.1 (ii), it follows that \(E(G[X\cup \{a_{1}, w, b_{1}, b_{2}, b_{3}\}])=\{a_{3} a_{2}, a_{2} a_{1}, a_{2}^{\prime} a_{1}, a_{1} w, w b_{1}, b_{1} b_{2}, b_{2} b_{3}\}\). Let now \(X^{\prime}=X\cup \{b_{2}, b_{3}\}\). We have \(X^{\prime}-N(X^{\prime})=\{a_{2}^{\prime}\}\). Let \(Y_{2}\) be as in Lemma 6.1 with \(X\) replaced by \(X^{\prime}\). By Lemma 6.3 (i) and (20), \(|Y_{2}|\le1+ 5\cdot 40<|N(w)|\). Let \(c_{1}\in N(w)-Y_{2}\), and take \(c_{2}\in N(c_{1})\cap N_{\ge 2}(w)\). Then \(E(G[\{a_{1}, b_{1}, w, c_{1}, c_{2}\}])=\{a_{1} w, b_{1} w, w c_{1}, c_{1} c_{2}\}\). Since \(E_{G}(X^{\prime}, \{w, c_{1}, c_{2}\})=\varnothing\) by Lemma 6.1 (i), we therefore see that \(X\cup \{a_{1}, w, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}\}\) induces a copy of \(T_{2}\). This contradicts the assumption that \(G\) is \(T_{2}\)-free, and completes the proof of Proposition 1.7.
