% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb,latexsym} \usepackage[dvipdfmx]{graphicx} %\usepackage{color} % we recommend the graphicx package for importing figures %\usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) %\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments %\theorembodyfont{\normalfont\slshape} \theoremstyle{plain} \newtheorem{thm}{Theorem}[section] \newtheorem{refthm}[thm]{Theorem} \newtheorem{Thm}{Theorem} \renewcommand{\theThm}{\Alph{Thm}} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{lem}[thm]{Lemma} \newtheorem{Q}[thm]{Question} %\newtheorem{Q}{Question} \renewcommand{\theQ}{} \newtheorem{claim}{Claim}[section] \newtheorem{subclaim}{Subclaim}[claim] %\renewcommand{\thesubclaim}{} \newtheorem{fact}[claim]{Fact} \newtheorem{con}[thm]{Conjecture} \newtheorem{pro}{Problem} %\newtheorem{theorem}{Theorem} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{fact}[theorem]{Fact} %\newtheorem{observation}[theorem]{Observation} %\newtheorem{claim}[theorem]{Claim} %\theoremstyle{definition} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{example}[theorem]{Example} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{open}[theorem]{Open Problem} %\newtheorem{problem}[theorem]{Problem} %\newtheorem{question}[theorem]{Question} %\theoremstyle{remark} %\newtheorem{remark}[theorem]{Remark} %\newtheorem{note}[theorem]{Note} \def\L{{ \mathcal{L}}} \def\T{{ \mathcal{T}}} \def\P{{ \mathcal{P}}} \def\F{{ \mathcal{F}}} \def\H{{ \mathcal{H}}} \def\C{{ \mathscr{C}}} \def\I{{ \mathcal{I}}} \def\Q{{ \mathcal{Q}}} \def\T{{ \mathcal{T}}} \def\G{{ \mathcal{G}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Forbidden triples generating a finite set \\ of $3$-connected graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Yoshimi Egawa\\ \small Dept. of Mathematical Information Science\\[-0.8ex] \small Tokyo University of Science\\[-0.8ex] \small 1-3 Kagurazaka, Shinjuku-ku\\[-0.8ex] \small Tokyo 162-8601, Japan\\ \and Jun Fujisawa\thanks{Supported by JSPS Grant-in-Aid for Young Scientists (B) (22740068) and Keio Gijuku Academic Development Funds.}\\ \small Faculty of Business and Commerce\\[-0.8ex] \small Keio University\\[-0.8ex] \small Hiyoshi 4-1-1, Kohoku-ku, Yokohama\\[-0.8ex] \small Kanagawa 223-8521, Japan\\ \small\tt fujisawa@fbc.keio.ac.jp\\ \and Michitaka Furuya\thanks{Supported by JSPS Grant-in-Aid for Young Scientists (B) (26800086).}\\ \small Dept. of Mathematical Information Science\\[-0.8ex] \small Tokyo University of Science\\[-0.8ex] \small 1-3 Kagurazaka, Shinjuku-ku\\[-0.8ex] \small Tokyo 162-8601, Japan\\ \small\tt michitaka.furuya@gmail.com\\ \and Michael D. Plummer\\ \small Dept. of Mathematics\\[-0.8ex] \small Vanderbilt University\\[-0.8ex] \small Nashville, Tennessee 37240, U.S.A\\ \small\tt michael.d.plummer@vanderbilt.edu\\ \and Akira Saito\thanks{Partially supposed by JSPS Grant-in-Aid for Scientific Research (C) (22500018).}\\ \small Dept. of Information Science\\[-0.8ex] \small Nihon University\\[-0.8ex] \small Sakurajousui 3-25-40, Setagaya-ku\\[-0.8ex] \small Tokyo 156-8550, Japan\\ \small\tt asaito@chs.nihon-u.ac.jp } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{}{}\\ \small Mathematics Subject Classifications: 05C75} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} For a graph $G$ and a set $\F$ of connected graphs, $G$ is said be $\F$-free if $G$ does not contain any member of $\F$ as an induced subgraph. We let $\G _{3}(\F)$ denote the set of all $3$-connected $\F$-free graphs. This paper is concerned with sets $\F$ of connected graphs such that $|\F|=3$ and $\G _{3}(\F)$ is finite. Among other results, we show that for an integer $m\geq 3$ and a connected graph $T$ of order greater than or equal to $4$, $\G _{3}(\{K_{4},K_{2,m},T\})$ is finite if and only if $T$ is a path of order $4$ or $5$. % keywords are optional \bigskip\noindent \textbf{Keywords:} forbidden subgraph; forbidden triple; $3$-connected graph \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction}\label{sec1} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this paper, we consider only finite undirected simple graphs. Let $\G$ denote the set of connected graphs with order greater than or equal to three. For a graph $G$ and for $F\in \G$, $G$ is said to be {\it $F$-free} if $G$ does not contain $F$ as an induced subgraph and, for $\F \subseteq \G$, $G$ is said to be {\it $\F$-free} if $G$ is $F$-free for every $F\in \F$. For an integer $k\geq 1$ and $\F\subseteq \G $, we let $\G _{k}$ denote the set of all $k$-connected graphs, and let $\G _{k}(\F)$ denote the set of all $\F$-free graphs belonging to $\G _{k}$. Thus $$ \G _{k}(\F):=\{G\mid G \mbox{ is a }k\mbox{-connected }\F\mbox{-free graph} \}. $$ This paper is concerned with subsets $\F$ of $\G$ such that $\G _{k}(\F)$ is a finite set. In this context, members of $\F$ are often referred to as forbidden subgraphs. For detailed historical background and related results, we refer the reader to \cite{FPS}. The following result can be found in \cite{D}. (Here $K_{n}$ denotes the complete graph of order $n$, $P_{l}$ denotes the path of order $l$ and, in general, $K_{m_{1},m_{2}}$ denotes the complete bipartite graph with partite sets having cardinalities $m_{1}$ and $m_{2}$.) \begin{Thm}[Diestel~\cite{D}; Chapter 9]%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{Diestel th} For $\F \subseteq \G $, $\G _{1}(\F)$ is finite if and only if $K_{n},K_{1,m},P_{l}\in \F $ for some integers $n\geq 3$, $m\geq 2$ and $l\geq 3$. \end{Thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% For $k\geq 2$, it is unlikely that a general result like Theorem~\ref{Diestel th} holds. Thus we confine ourselves to the case where $|\F|$ is ``small''. It is known that for any $k\geq 2$, there is no $\F \subseteq \G $ with $|\F|=1$ such that $\G _{k}(\F)$ is finite. (See \cite{FPS}; Theorem 2.) Further, those subsets $\F$ of $\G$ with $|\F|=2$ for which $\G_{k}(\F)$ is finite are determined for $k\leq 6$ in \cite{FPS}. Here we are interested in the case where $|\F|=3$. Note that a connected $K_{1,2}$-free graph is a complete graph. Hence if $K_{1,2}\in \F$, then $\G _{k}(\F)$ is finite if and only if $K_{n}\in \F$ for some $n\geq 3$, and there is no point in forbidding two more graphs. %Note that for an integer $k\geq 2$ and a subset $\F$ of $\G$ with $K_{1,2}\in \F$, $\G _{k}(\F)$ is finite if and only if $K_{n}\in \F $ for some $n\geq 3$. Thus when we discuss $\G _{k}(\F)$ with $|\F|=3$, we usually assume $K_{1,2}\not\in \F$. For $k=2$, the following theorem is proved in \cite{FPS}. \begin{Thm}[Fujisawa, Plummer and Saito~\cite{FPS}]%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{tri 2-conn} Let $\F$ be a subset of $\G$ with $|\F|=3$ and $K_{1,2}\not\in \F$. Then $\G _{2}(\F)$ is finite if and only if one of the following holds: \begin{enumerate} \item[{\upshape(i)}] $\F =\{K_{3},K_{2,m},P_{l}\}$ for some integers $m$ and $l$ with $m\geq 3$ and $4\leq l\leq 5$; \item[{\upshape(ii)}] $\F =\{K_{3},K_{2,2},P_{6}\}$; or \item[{\upshape(iii)}] $\F =\{K_{n},K_{1,m},P_{l}\}$ for some integers $n$, $m$ and $l$ with $n\geq 3$, $m\geq 3$ and $l\geq 4$. \end{enumerate} \end{Thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In the present paper, we investigate the case where $|\F|=3$ and $k=3$. It is easy to see $\G _{3}(\{K_{3},K_{1,3}\})=\emptyset $. (See \cite{FPS}.) %Note that $\G _{3}(\{K_{3},K_{1,3}\})=\emptyset $. Thus when we consider $\G _{3}(\F)$, we assume that $\{K_{3},K_{1,3}\}\not\subseteq \F $, in addition to the condition that $K_{1,2}\not\in \F $. Before stating our results, we make some more definitions. Let $n$ be an integer with $n\geq 2$. Let $P=x_{1}x_{2}\cdots x_{n}$ be the path of order $n$, and let $y_{1}$, $y_{2}$, $z_{1}$ and $z_{2}$ be four distinct vertices different from $x_{1},\ldots ,x_{n}$. We let $Y_{n}$, $Y^{*}_{n}$, $Q_{n}$ and $Q^{*}_{n}$ denote the graphs defined by $$ V(Y_{n})=V(Q_{n})=V(P)\cup \{y_{1},y_{2}\},~~~V(Y^{*}_{n})=V(Q^{*}_{n})=V(P)\cup \{y_{1},y_{2},z_{1},z_{2}\}, $$ $$ E(Y_{n})=E(P)\cup \{x_{1}y_{1},x_{1}y_{2}\},~~~E(Y^{*}_{n})=E(P)\cup \{x_{1}y_{1},x_{1}y_{2},x_{n}z_{1},x_{n}z_{2}\}, $$ $$ E(Q_{n})=E(Y_{n})\cup \{y_{1}y_{2}\} \mbox{ ~~and~~ } E(Q^{*}_{n})=E(Y^{*}_{n})\cup \{y_{1}y_{2},z_{1}z_{2}\} $$ (see Figure~\ref{f1}). \begin{figure} \begin{center} %WinTpicVersion4.10 \unitlength 0.1in \begin{picture}( 40.6000, 13.0000)( -0.1000,-16.5000) % CIRCLE 2 0 0 0 Black Black % 4 400 400 400 450 400 450 400 450 % \special{sh 1.000}% \special{ia 400 400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 400 400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 400 800 400 850 400 850 400 850 % \special{sh 1.000}% \special{ia 400 800 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 400 800 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 800 600 800 650 800 650 800 650 % \special{sh 1.000}% \special{ia 800 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 800 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1200 600 1200 650 1200 650 1200 650 % \special{sh 1.000}% \special{ia 1200 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1200 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1600 600 1600 650 1600 650 1600 650 % \special{sh 1.000}% \special{ia 1600 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1600 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2400 400 2400 450 2400 450 2400 450 % \special{sh 1.000}% \special{ia 2400 400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2400 400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2400 800 2400 850 2400 850 2400 850 % \special{sh 1.000}% \special{ia 2400 800 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2400 800 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2800 600 2800 650 2800 650 2800 650 % \special{sh 1.000}% \special{ia 2800 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2800 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3200 600 3200 650 3200 650 3200 650 % \special{sh 1.000}% \special{ia 3200 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3200 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3600 600 3600 650 3600 650 3600 650 % \special{sh 1.000}% \special{ia 3600 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3600 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4000 400 4000 450 4000 450 4000 450 % \special{sh 1.000}% \special{ia 4000 400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4000 400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4000 800 4000 850 4000 850 4000 850 % \special{sh 1.000}% \special{ia 4000 800 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4000 800 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black White % 16 400 400 800 600 800 600 400 800 800 600 1600 600 2400 400 2800 600 2800 600 2400 800 2800 600 3600 600 3600 600 4000 400 4000 800 3600 600 % \special{pn 8}% \special{pa 400 400}% \special{pa 800 600}% \special{fp}% \special{pa 800 600}% \special{pa 400 800}% \special{fp}% \special{pa 800 600}% \special{pa 1600 600}% \special{fp}% \special{pa 2400 400}% \special{pa 2800 600}% \special{fp}% \special{pa 2800 600}% \special{pa 2400 800}% \special{fp}% \special{pa 2800 600}% \special{pa 3600 600}% \special{fp}% \special{pa 3600 600}% \special{pa 4000 400}% \special{fp}% \special{pa 4000 800}% \special{pa 3600 600}% \special{fp}% % CIRCLE 2 0 0 0 Black Black % 4 400 1200 400 1250 400 1250 400 1250 % \special{sh 1.000}% \special{ia 400 1200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 400 1200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 400 1600 400 1650 400 1650 400 1650 % \special{sh 1.000}% \special{ia 400 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 400 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 800 1400 800 1450 800 1450 800 1450 % \special{sh 1.000}% \special{ia 800 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 800 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1200 1400 1200 1450 1200 1450 1200 1450 % \special{sh 1.000}% \special{ia 1200 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1200 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1600 1400 1600 1450 1600 1450 1600 1450 % \special{sh 1.000}% \special{ia 1600 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1600 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2400 1200 2400 1250 2400 1250 2400 1250 % \special{sh 1.000}% \special{ia 2400 1200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2400 1200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2400 1600 2400 1650 2400 1650 2400 1650 % \special{sh 1.000}% \special{ia 2400 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2400 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2800 1400 2800 1450 2800 1450 2800 1450 % \special{sh 1.000}% \special{ia 2800 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2800 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3200 1400 3200 1450 3200 1450 3200 1450 % \special{sh 1.000}% \special{ia 3200 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3200 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3600 1400 3600 1450 3600 1450 3600 1450 % \special{sh 1.000}% \special{ia 3600 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3600 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4000 1200 4000 1250 4000 1250 4000 1250 % \special{sh 1.000}% \special{ia 4000 1200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4000 1200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4000 1600 4000 1650 4000 1650 4000 1650 % \special{sh 1.000}% \special{ia 4000 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4000 1600 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black White % 16 400 1200 800 1400 800 1400 400 1600 800 1400 1600 1400 2400 1200 2800 1400 2800 1400 2400 1600 2800 1400 3600 1400 3600 1400 4000 1200 4000 1600 3600 1400 % \special{pn 8}% \special{pa 400 1200}% \special{pa 800 1400}% \special{fp}% \special{pa 800 1400}% \special{pa 400 1600}% \special{fp}% \special{pa 800 1400}% \special{pa 1600 1400}% \special{fp}% \special{pa 2400 1200}% \special{pa 2800 1400}% \special{fp}% \special{pa 2800 1400}% \special{pa 2400 1600}% \special{fp}% \special{pa 2800 1400}% \special{pa 3600 1400}% \special{fp}% \special{pa 3600 1400}% \special{pa 4000 1200}% \special{fp}% \special{pa 4000 1600}% \special{pa 3600 1400}% \special{fp}% % LINE 2 0 3 0 Black White % 6 400 1200 400 1600 2400 1600 2400 1200 4000 1200 4000 1600 % \special{pn 8}% \special{pa 400 1200}% \special{pa 400 1600}% \special{fp}% \special{pa 2400 1600}% \special{pa 2400 1200}% \special{fp}% \special{pa 4000 1200}% \special{pa 4000 1600}% \special{fp}% % STR 2 0 3 0 Black White % 4 200 500 200 600 5 0 0 0 % $Y_{3}$ \put(2.0000,-6.0000){\makebox(0,0){$Y_{3}$}}% % STR 2 0 3 0 Black White % 4 200 1300 200 1400 5 0 0 0 % $Q_{3}$ \put(2.0000,-14.0000){\makebox(0,0){$Q_{3}$}}% % STR 2 0 3 0 Black White % 4 2200 500 2200 600 5 0 0 0 % $Y^{*}_{3}$ \put(22.0000,-6.0000){\makebox(0,0){$Y^{*}_{3}$}}% % STR 2 0 3 0 Black White % 4 2200 1300 2200 1400 5 0 0 0 % $Q^{*}_{3}$ \put(22.0000,-14.0000){\makebox(0,0){$Q^{*}_{3}$}}% \end{picture}% \caption{Graphs $Y_{3}$, $Y^{*}_{3}$, $Q_{3}$ and $Q^{*}_{3}$} \label{f1} \end{center} \end{figure} A {\it caterpillar} is a tree for which the removal of all endvertices leaves a path. A complete bipartite graph of the form $K_{1,m}$ with $m\geq 1$ is called a {\it star}. Let $\T _{0}$ be the set of trees in $\G -\{K_{1,2},K_{1,3}\}$ having maximum degree at most $3$. Note that $\T _{0}$ does not contain a star. Let $\T _{1}$ be the set of those caterpillars belonging to $\T _{0}$ in which no two vertices of degree $3$ are adjacent. Let $\T _{2}=\{P_{l},Y_{m},Y^{*}_{n}\mid l\geq 4,m\geq 3,n\geq 3\}$. We have $\T _{0}\supseteq \T _{1}\supseteq \T _{2}$. Let $G$ be a connected graph. A vertex $v$ of $G$ is called a {\it cutvertex} if $G-v$ is disconnected. If $G$ has a cutvertex, $G$ is said to be {\it separable}; otherwise, it is said to be {\it nonseparable}. Note that $K_{1}$ is a nonseparable graph. A maximal nonseparable subgraph of $G$ is called a {\it block} of $G$. When $G$ is separable, the {\it block-cutvertex graph} of $G$ is defined to be the bipartite graph $Z$ such that $Z$ has as its partite sets the set of all cutvertices of $G$ and the set of all blocks of $G$ and, for a cutvertex $v$ and a block $B$, $v$ and $B$ are adjacent in $Z$ if and only if $v$ is a vertex of $B$ in $G$. It is a well-known fact that the block-cutvertex graph of a connected graph is a tree. A {\it cactus} is a connected graph every block of which is a complete graph of order two or a cycle. Let $\T ^{*}_{0}$ be the set of those cacti $T$ in $\G -\{K_{1,2},K_{3}\}$ such that all cycles of $T$ are triangles and in the block-cutvertex graph of $T$, the distance between any two vertices corresponding to triangles of $T$ is a multiple of $4$. Let $\T ^{*}_{1}$ be the set of those members of $\T ^{*}_{0}$ whose block-cutvertex graph is a path. Let $\T ^{*}_{2}=\{P_{l},Q_{m},Q^{*}_{2n}\mid l\geq 4,m\geq 2,n\geq 1\}$. We have $\T ^{*}_{0}\supseteq \T ^{*}_{1}\supseteq \T ^{*}_{2}$. Our main result is as follows. \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{nec} Let $\F $ be a subset of $\G $ with $|\F |=3$, $K_{1,2}\not\in \F $ and $\{K_{1,3},K_{3}\}\not\subseteq \F $, and suppose that $\G _{3}(\F )$ is finite. Then one of the following holds: \begin{enumerate} \item[{\upshape(i)}] $\F =\{K_{3},K_{3,m},T\}$ with $m\geq 3$, where $T\in \T _{2}$; \item[{\upshape(ii)}] $\F =\{K_{4},K_{2,m},T\}$ with $m\geq 2$, where $T$ is a path; \item[{\upshape(iii)}] $\F =\{K_{3},K_{2,m},T\}$ with $m\geq 2$, where $T\in \T _{0}$ in the case where $m=2$, $T\in \T _{1}$ in the case where $3\leq m\leq 4$, and $T\in \T _{2}$ in the case where $m\geq 5$; \item[{\upshape(iv)}] $\F =\{K_{n},K_{1,m},T\}$ with $n\geq 4$ and $m\geq 4$, where $T$ is a path; \item[{\upshape(v)}] $\F =\{K_{3},K_{1,m},T\}$ with $m\geq 4$, where $T\in \T _{1}$ in the case where $m=4$, and $T\in \T _{2}$ in the case where $m\geq 5$; or \item[{\upshape(vi)}] $\F =\{K_{n},K_{1,3},T\}$ with $n\geq 4$, where $T\in \T ^{*}_{1}$ in the case where $n=4$, and $T\in \T ^{*}_{2}$ in the case where $n\geq 5$. \end{enumerate} \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The converse of Theorem~\ref{nec} does not hold. However, if (iv) of Theorem~\ref{nec} holds, then $\G _{3}(\F)$ is finite by Theorem~\ref{Diestel th}. Also, as we shall state below in Theorem~\ref{ns4}, if (v) holds with $m\geq 5$, then $\G _{3}(\F)$ is finite. Further when $m$ is ``large'' in cases (i) through (iii) of Theorem~\ref{nec}, we can determine $T$ as follows. \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns1} Let $m$ be an integer with $m\geq 4$, and let $T\in \G-\{K_{1,2},K_{1,3}\}$. Then $\G _{3}(\{K_{3},K_{3,m},T\})$ is finite if and only if $T$ is a path of order $4$ or $5$ or $T=Y_{3}$. \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns2} Let $m$ be an integer with $m\geq 3$, and let $T\in \G-\{K_{1,2}\}$. Then $\G _{3}(\{K_{4},K_{2,m},T\})$ is finite if and only if $T$ is a path of order $4$ or $5$. \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns3} Let $m$ be an integer with $m\geq 5$, and let $T\in \G-\{K_{1,2},K_{1,3}\}$. Then $\G _{3}(\{K_{3},K_{2,m},T\})$ is finite if and only if $T$ is either a path of order at most $7$ or an induced subgraph of $Y^{*}_{3}$. \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thm}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns4} Let $m$ be an integer with $m\geq 5$, and let $T\in \G-\{K_{1,2},K_{1,3}\}$. Then $\G _{3}(\{K_{3},K_{1,m},T\})$ is finite if and only if $T\in \T _{2}$. \end{thm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We prove Theorem~\ref{nec} in Section~\ref{sec2}. We prove Theorem~\ref{ns1} in Section~\ref{sec3}, Theorem~\ref{ns2} in Section~\ref{sec4}, Theorem~\ref{ns4} in Section~\ref{sec5}, and Theorem~\ref{ns3} in Section~\ref{sec6}. Our notation and terminology are standard, and mostly taken from \cite{D}. Exceptions are as follows. Let $G$ be a graph. For $u,v\in V(G)$, $d(u,v)$ denotes the distance between $u$ and $v$. When $G$ is connected, we define the {\it diameter} $\mbox{diam}(G)$ of $G$ by $\mbox{diam}(G)=\max\{d(u,v)\mid u,v\in V(G)\}$. Let $u\in V(G)$. For an integer $i\geq 1$, we let $N_{i}(u)=\{x\in V(G)\mid d(u,x)=i\}$. We write $N(u)$ for $N_{1}(u)$. We let $d(u)$ denote the degree of $u$; thus $d(u)=|N(u)|$. When we need to specify that the underlying graph is $G$, we write $N_{G}(u)$ and $d_{G}(u)$ for $N(u)$ and $d(u)$, respectively. We let $\Delta (G)=\max\{d(u)\mid u\in V(G)\}$. For $Y\subseteq V(G)$, we let $N(Y)$ denote the union of $N(u)$ as $u$ ranges over $Y$. For $X,Y\subseteq V(G)$ with $X\cap Y=\emptyset $, $E(X,Y)$ denotes the set of edges joining a vertex in $X$ and a vertex in $Y$. When $G$ is connected, a block of $G$ containing at most one cutvertex of $G$ is called an {\it endblock} of $G$. When $G$ is not necessarily connected, by a cutvertex of $G$, we mean a cutvertex of a component of $G$. Similarly, by a block (resp. an endblock) of $G$, we mean a block (resp. an endblock) of a component of $G$. Note that isolated vertices of $G$ are endblocks of $G$. For an endblock $B$ of $G$, a vertex of $B$ which is not a cutvertex of $G$ is called an {\it internal vertex} of $B$. For a graph $H$ and an integer $s\geq 2$, we let $sH$ denote the disjoint union of $s$ copies of $H$. For two graphs $H_{1}$ and $H_{2}$, we let $H_{1}+H_{2}$ denote the join of $H_{1}$ and $H_{2}$. Finally for $s\geq 4$, $C_{s}$ denotes the cycle of order $s$ and, for $t\geq 5$, we let $W_{t}=C_{t-1}+K_{1}$ denote the {\it wheel graph} of order $t$. In subsequent arguments, when we prove the finiteness of $\G _{3}(\F)$ for a given family $\F$, we bound the diameter and the maximum degree of a graph $G$ in $\G _{3}(\F)$ from above, and then bound the order in terms of the diameter and the maximum degree. For this purpose, we make one easy observation. \begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{new diam lem} Let $m\geq 2$ and $k\geq 3$, and let $G$ be a graph with $\Delta (G)\leq m$ and $\mbox{diam}(G)\leq k$. Then $|V(G)|\leq m^{k}$. \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $w\in V(G)$. Then $|N_{i}(w)|\leq m(m-1)^{i-1}$ for each $1\leq i\leq k$. Hence $|V(G)|\leq 1+m+(\sum_{2\leq i\leq k-1}m(m-1)^{i-1})+m(m-1)^{k-1}\leq m^{k-1}+(\sum_{2\leq i\leq k-1}m^{k-i}(m-1)^{i-1})+m(m-1)^{k-1}=m^{k}$. \qed The bound $m^{k}$ in the above lemma is far from sharp, but we use it for the sake of brevity. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A necessary condition}\label{sec2} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we prove Theorem~\ref{nec}. We start with several lemmas. The first two lemmas are proved in \cite{K} and \cite{FPS}, respectively. \begin{lem}[Kochol~\cite{K}]%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{nec lem1} For every integer $g\geq 3$, there exists a $3$-connected $3$-regular graph with girth $g$. In particular, for every integer $g\geq 3$, there exist infinitely many $3$-connected $3$-regular graphs with girth at least $g$. \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lem}[Fujisawa, Plummer and Saito~\cite{FPS}]%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{nec lem2} For $\F \subseteq \G$, if $\G _{3}(\F )$ is finite, then $\{K_{n},K_{m_{1},m_{2}}\}\subseteq \F $ for some integers $n$, $m_{1}$ and $m_{2}$ with $n\geq 3$, $m_{2}\geq m_{1}\geq 1$ and $m_{1}\leq 3$. \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{nec lem3} Let $\F $ be a finite subset of $\G -\{K_{1,2},K_{1,3}\}$, and suppose that $\G _{3}(\F)$ is finite. Then $\F $ contains a member of $\T _{0}$. \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $t=\max \{|V(F)|\mid F\in \F \}$, and let $\H =\{G\in \G _{3}\mid G$ is a $3$-regular graph with girth at least $t+1\}$. By Lemma~\ref{nec lem1}, $\H $ is an infinite set. Since $\G _{3}(\F )$ is finite and $\H $ is infinite, there exists $G\in \H $ such that $G$ contains a graph $F$ in $\F $ as an induced subgraph. Since the girth of $G$ is strictly greater than $|V(F)|$, $F$ is a tree. Since $G$ is $3$-regular and since $F\not=K_{1,2},K_{1,3}$ by the assumption that $\F \subseteq \G -\{K_{1,2},K_{1,3}\}$, it follows that $F\in \T _{0}$. \qed \begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{nec lem4} Let $m_{1}$ and $m_{2}$ be integers such that $m_{2}\geq m_{1}\geq 1$, $m_{1}\leq 3$ and $(m_{1},m_{2})\not=(1,2),(1,3),(2,2)$, and let $T\in \G -\{K_{1,2},K_{1,3}\}$. Set $\F =\{K_{3},K_{m_{1},m_{2}},T\}$, and suppose that $\G _{3}(\F )$ is finite. Then the following hold. \begin{enumerate} \item[{\upshape(i)}] We have $T\in \T _{1}$. \item[{\upshape(ii)}] If in addition, $(m_{1},m_{2})\not\in \{(1,4),(2,3),(2,4)\}$, then $T\in \T _{2}$. \end{enumerate} \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof By Lemma~\ref{nec lem3}, $T\in \T_{0}$. \begin{enumerate} \item[{\upshape(i)}] For each $s\geq 5$, the Cartesian product $C_{s}\times K_{2}$ is $3$-connected and $\{K_{3},K_{m_{1},m_{2}}\}$-free. %For each $s\geq 5$, $C_{s}\times K_{2}$ is $3$-connected and $\{K_{3},K_{m_{1},m_{2}}\}$-free, where $C_{s}\times K_{2}$ denotes the Cartesian product of $C_{s}$ and $K_{2}$. Since $\G _{3}(\F )$ is finite, this implies that there exists $s\geq 5$ such that $C_{s}\times K_{2}$ contains $T$ as an induced subgraph. Since every member of $\T _{0}$ contained in $C_{s}\times K_{2}$ as an induced subgraph belongs to $\T _{1}$, $T\in \T _{1}$. \item[{\upshape(ii)}] By (i), $T\in \T _{1}$. For each $s\geq 5$, let $C'_{s}$ denote the so-called lexicographic product of $C_{s}$ and the null graph of order two; that is to say, $V(C'_{s})=\{x_{i,j}\mid 1\leq i\leq s,1\leq j\leq 2\}$ and $E(C'_{s})=\{x_{i,j}x_{i+1,h}\mid 1\leq i\leq s,1\leq j,h\leq 2\}$, where first indices of the letter $x$ are to be read modulo $s$. Then $C'_{s}$ is $3$-connected and $\{K_{3},K_{m_{1},m_{2}}\}$-free. Hence there exists $s\geq 5$ such that $C'_{s}$ contains $T$ as an induced subgraph. Since every member of $\T _{1}$ contained in $C'_{s}$ as an induced subgraph belongs to $\T _{2}$, $T\in \T _{2}$. \qed \end{enumerate} \medbreak\noindent\textit{Proof of Theorem~\ref{nec}.}\quad Let $\F $ be as in Theorem~\ref{nec}. By Lemma~\ref{nec lem2}, $\{K_{n},K_{m_{1},m_{2}}\}\subseteq \F $ for some integers $n$, $m_{1}$ and $m_{2}$ with $n\geq 3$, $m_{2}\geq m_{1}\geq 1$ and $m_{1}\leq 3$. Write $\F =\{K_{n},K_{m_{1},m_{2}},T\}$. \medskip \noindent \textbf{Case 1:} $\F $ contains no star In this case, $2\leq m_{1}\leq 3$, and we have $T\in \T _{0}$ by Lemma~\ref{nec lem3}. \medskip \noindent \textbf{Subcase 1.1:} $m_{1}=3$ For each $s\geq 3$, $P_{3}+sK_{1}$ is $3$-connected and $K_{3,m_{2}}$-free. Since $T$ is not a star and every tree contained in $P_{3}+sK_{1}$ as an induced subgraph is a star, $P_{3}+sK_{1}$ is also $T$-free. Since $\G _{3}(\F )$ is finite, this implies that there exists $s\geq 3$ such that $P_{3}+sK_{1}$ contains $K_{n}$ as an induced subgraph. Since $P_{3}+sK_{1}$ is $K_{4}$-free, this forces $n=3$. Now by Lemma~\ref{nec lem4}(ii), $T\in \T _{2}$, and hence (i) of Theorem~\ref{nec} holds. \medskip \noindent \textbf{Subcase 1.2:} $m_{1}=2$ and $n\geq 4$ For each $s\geq 3$, $K_{3}+sK_{1}$ is $3$-connected and $K_{2,m_{2}}$-free. Since every tree contained in $K_{3}+sK_{1}$ as an induced subgraph is a star, $K_{3}+sK_{1}$ is also $T$-free. Hence there exists $s\geq 3$ such that $K_{3}+sK_{1}$ contains $K_{n}$ as an induced subgraph, which implies $n=4$. For each $t\geq 6$, $W_{t}$ is $3$-connected and $\{K_{4},K_{2,m_{2}}\}$-free. Hence there exists $t\geq 6$ such that $W_{t}$ contains $T$ as an induced subgraph. Since $T\in \T _{0}$ and every member of $\T _{0}$ contained in $W_{t}$ as an induced subgraph is a path, $T$ is a path. Consequently (ii) of Theorem~\ref{nec} holds. \medskip \noindent \textbf{Subcase 1.3:} $m_{1}=2$ and $n=3$ Recall that $T\in \T _{0}$. Also if $3\leq m_{2}\leq 4$, then $T\in \T _{1}$ by Lemma~\ref{nec lem4}(i); if $m_{2}\geq 5$, then $T\in \T _{2}$ by Lemma~\ref{nec lem4}(ii). Thus (iii) of Theorem~\ref{nec} holds. \medskip \noindent \textbf{Case 2:} $\F $ contains a star Interchanging the roles of $K_{m_{1},m_{2}}$ and $T$ with each other if necessary, we may assume that $K_{m_{1},m_{2}}$ is the star of the smallest order contained in $\F $. Then $m_{1}=1$, and $m_{2}\geq 3$ by the assumption that $K_{1,2}\not\in \F $, and $T\not=K_{1,2},K_{1,3}$ by the minimality of $m_{2}$. \medskip \noindent \textbf{Subcase 2.1:} $m_{2}\geq 4$ By Lemma~\ref{nec lem3}, $T\in \T _{0}$. \medskip \noindent \textbf{Subcase 2.1.1:} $n\geq 4$ For each $s\geq 7$, let $C_{s}^{2}$ denote the square of $C_{s}$; that is to say $V(C_{s}^{2})=\{x_{i}\mid 1\leq i\leq s\}$ and $E(C_{s}^{2})=\{x_{i}x_{i+1},x_{i}x_{i+2}\mid 1\leq i\leq s\}$, where indices of the letter $x$ are to be read modulo $s$. Then $C_{s}^{2}$ is $3$-connected and $\{K_{n},K_{1,m_{2}}\}$-free. Hence there exists $s\geq 7$ such that $C_{s}^{2}$ contains $T$ as an induced subgraph. Since every tree contained in $C_{s}^{2}$ as an induced subgraph is a path, $T$ is a path. Hence (iv) of Theorem~\ref{nec} holds. \medskip \noindent \textbf{Subcase 2.1.2:} $n=3$ If $m_{2}=4$, then $T\in \T _{1}$ by Lemma~\ref{nec lem4}(i); if $m_{2}\geq 5$, then $T\in \T _{2}$ by Lemma~\ref{nec lem4}(ii). Thus (v) of Theorem~\ref{nec} holds. \medskip \noindent \textbf{Subcase 2.2:} $m_{2}=3$ By the assumption that $\{K_{1,3},K_{3}\}\not\subseteq \F $, we have $n\geq 4$ and $T\not=K_{3}$. Thus $T\in \G -\{K_{1,2},K_{1,3},K_{3}\}$. For a $3$-connected $3$-regular graph $G$, let $H_{G}$ be the graph obtained by expanding each vertex of $G$ to a triangle (see Figure~\ref{f5}); more precisely, we define $H_{G}$ by $V(H_{G})=\{x_{u,v}\mid (u,v)\in V(G)\times V(G), uv\in E(G)\}$ and $E(H_{G})=\{x_{u,v}x_{u,w}\mid u\in V(G),v,w\in N(u),v\not=w\}\cup \{x_{u,v}x_{v,u}\mid uv\in E(G)\}$. Then $H_{G}$ is $3$-connected $3$-regular and $\{K_{n},K_{1,3}\}$-free and, for $u\in V(G)$, $B_{u}=x_{u,v_{1}}x_{u,v_{2}}x_{u,v_{3}}x_{u,v_{1}}$ $(\{v_{1},v_{2},v_{3}\}=N(u))$ is a triangle of $H_{G}$. Also each cycle of $H_{G}$ which is not of the form $B_{u}$ with $u\in V(G)$ has length at least twice as large as the girth of $G$ and, for any $u,u'\in V(G)$ with $u\not=u'$, every induced path in $H_{G}$ joining $B_{u}$ and $B_{u'}$ has even order. Hence every induced connected subgraph of $H_{G}$ having order greater than or equal to four and strictly less than twice the girth of $G$ belongs to $\T ^{*}_{0}$. On the other hand, by Lemma~\ref{nec lem1}, the set $\{H_{G}\mid G$ is a $3$-connected $3$-regular graph with girth at least $(|V(T)|+1)/2\}$ is an infinite set. Hence there exists a $3$-connected $3$-regular graph $G$ with girth at least $(|V(T)|+1)/2$ such that $H_{G}$ contains $T$ as an induced subgraph. Note that $|V(T)|$ is less than twice the girth of $G$. Consequently $T\in \T ^{*}_{0}$. \begin{figure} \begin{center} %WinTpicVersion4.10 \unitlength 0.1in \begin{picture}( 49.7500, 15.0000)( 1.0500,-17.5000) % CIRCLE 2 0 0 0 Black Black % 4 1200 1000 1200 1050 1200 1050 1200 1050 % \special{sh 1.000}% \special{ia 1200 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1200 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 600 600 600 650 600 650 600 650 % \special{sh 1.000}% \special{ia 600 600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 600 600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2000 1000 2000 1050 2000 1050 2000 1050 % \special{sh 1.000}% \special{ia 2000 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2000 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 600 1400 600 1450 600 1450 600 1450 % \special{sh 1.000}% \special{ia 600 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 600 1400 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 18 600 1400 1200 1000 1200 1000 2000 1000 2000 1000 2200 800 2200 1200 2000 1000 1200 1000 600 600 600 600 600 400 600 600 400 600 400 1400 600 1400 600 1400 600 1600 % \special{pn 8}% \special{pa 600 1400}% \special{pa 1200 1000}% \special{fp}% \special{pa 1200 1000}% \special{pa 2000 1000}% \special{fp}% \special{pa 2000 1000}% \special{pa 2200 800}% \special{fp}% \special{pa 2200 1200}% \special{pa 2000 1000}% \special{fp}% \special{pa 1200 1000}% \special{pa 600 600}% \special{fp}% \special{pa 600 600}% \special{pa 600 400}% \special{fp}% \special{pa 600 600}% \special{pa 400 600}% \special{fp}% \special{pa 400 1400}% \special{pa 600 1400}% \special{fp}% \special{pa 600 1400}% \special{pa 600 1600}% \special{fp}% % CIRCLE 2 0 0 0 Black Black % 4 3500 700 3500 750 3500 750 3500 750 % \special{sh 1.000}% \special{ia 3500 700 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3500 700 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4650 1000 4650 1050 4650 1050 4650 1050 % \special{sh 1.000}% \special{ia 4650 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4650 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4100 1000 4100 1050 4100 1050 4100 1050 % \special{sh 1.000}% \special{ia 4100 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4100 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3900 850 3900 900 3900 900 3900 900 % \special{sh 1.000}% \special{ia 3900 850 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3900 850 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3900 1150 3900 1200 3900 1200 3900 1200 % \special{sh 1.000}% \special{ia 3900 1150 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3900 1150 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3500 450 3500 500 3500 500 3500 500 % \special{sh 1.000}% \special{ia 3500 450 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3500 450 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3250 700 3250 750 3250 750 3250 750 % \special{sh 1.000}% \special{ia 3250 700 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3250 700 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3250 1300 3250 1350 3250 1350 3250 1350 % \special{sh 1.000}% \special{ia 3250 1300 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3250 1300 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3500 1300 3500 1350 3500 1350 3500 1350 % \special{sh 1.000}% \special{ia 3500 1300 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3500 1300 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3500 1550 3500 1600 3500 1600 3500 1600 % \special{sh 1.000}% \special{ia 3500 1550 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3500 1550 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4880 1150 4880 1200 4880 1200 4880 1200 % \special{sh 1.000}% \special{ia 4880 1150 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4880 1150 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4880 850 4880 900 4880 900 4880 900 % \special{sh 1.000}% \special{ia 4880 850 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4880 850 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 42 4880 850 4650 1000 4650 1000 4880 1150 4880 1150 4880 850 4650 1000 4100 1000 4100 1000 3900 850 3900 850 3900 1150 3900 1150 4100 1000 3900 850 3500 700 3500 700 3500 450 3500 700 3250 700 3250 700 3500 450 3500 450 3500 250 3250 700 3050 700 3050 1300 3250 1300 3250 1300 3500 1300 3500 1300 3500 1550 3500 1550 3250 1300 3500 1550 3500 1750 3500 1300 3900 1150 4880 1150 5080 1350 4880 850 5080 650 % \special{pn 8}% \special{pa 4880 850}% \special{pa 4650 1000}% \special{fp}% \special{pa 4650 1000}% \special{pa 4880 1150}% \special{fp}% \special{pa 4880 1150}% \special{pa 4880 850}% \special{fp}% \special{pa 4650 1000}% \special{pa 4100 1000}% \special{fp}% \special{pa 4100 1000}% \special{pa 3900 850}% \special{fp}% \special{pa 3900 850}% \special{pa 3900 1150}% \special{fp}% \special{pa 3900 1150}% \special{pa 4100 1000}% \special{fp}% \special{pa 3900 850}% \special{pa 3500 700}% \special{fp}% \special{pa 3500 700}% \special{pa 3500 450}% \special{fp}% \special{pa 3500 700}% \special{pa 3250 700}% \special{fp}% \special{pa 3250 700}% \special{pa 3500 450}% \special{fp}% \special{pa 3500 450}% \special{pa 3500 250}% \special{fp}% \special{pa 3250 700}% \special{pa 3050 700}% \special{fp}% \special{pa 3050 1300}% \special{pa 3250 1300}% \special{fp}% \special{pa 3250 1300}% \special{pa 3500 1300}% \special{fp}% \special{pa 3500 1300}% \special{pa 3500 1550}% \special{fp}% \special{pa 3500 1550}% \special{pa 3250 1300}% \special{fp}% \special{pa 3500 1550}% \special{pa 3500 1750}% \special{fp}% \special{pa 3500 1300}% \special{pa 3900 1150}% \special{fp}% \special{pa 4880 1150}% \special{pa 5080 1350}% \special{fp}% \special{pa 4880 850}% \special{pa 5080 650}% \special{fp}% % VECTOR 0 0 3 0 Black Black % 2 2400 1000 3000 1000 % \special{pn 20}% \special{pa 2400 1000}% \special{pa 3000 1000}% \special{fp}% \special{sh 1}% \special{pa 3000 1000}% \special{pa 2934 980}% \special{pa 2948 1000}% \special{pa 2934 1020}% \special{pa 3000 1000}% \special{fp}% % STR 2 0 3 0 Black Black % 4 200 300 200 400 5 0 0 0 % $G$ \put(2.0000,-4.0000){\makebox(0,0){$G$}}% % STR 2 0 3 0 Black Black % 4 3000 300 3000 400 5 0 0 0 % $H_{G}$ \put(30.0000,-4.0000){\makebox(0,0){$H_{G}$}}% \end{picture}% \caption{Graph $H_{G}$} \label{f5} \end{center} \end{figure} Further for each $s\geq 7$, $C_{s}^{2}$ is $3$-connected and $\{K_{n},K_{1,3}\}$-free. Hence there exists $s\geq 7$ such that $C_{s}^{2}$ contains $T$ as an induced subgraph. Since every member of $\T ^{*}_{0}$ contained in $C_{s}^{2}$ as an induced subgraph belongs to $\T ^{*}_{1}$, $T\in \T ^{*}_{1}$. Now assume $n\geq 5$. For each $s\geq 4$, let $C^{*}_{s}$ denote the lexicographic product of $C_{s}$ and $K_{2}$; that is to say, $V(C^{*}_{s})=\{x_{i,j}\mid 1\leq i\leq s,1\leq j\leq 2\}$ and $E(C^{*}_{s})=\{x_{i,j}x_{i+1,h},x_{i,1}x_{i,2}\mid 1\leq i\leq s,1\leq j,h\leq 2\}$, where first indices of the letter $x$ are to be read modulo $s$. Then $C^{*}_{s}$ is $3$-connected and $\{K_{n},K_{1,3}\}$-free. Hence there exists $s\geq 4$ such that $C^{*}_{s}$ contains $T$ as an induced subgraph. Since every member of $\T ^{*}_{1}$ contained in $C^{*}_{s}$ as an induced subgraph belongs to $\T ^{*}_{2}$, $T\in \T ^{*}_{2}$. Thus we have $T\in \T ^{*}_{1}$ if $n=4$, and $T\in \T ^{*}_{2}$ if $n\geq 5$. Hence (vi) of Theorem~\ref{nec} holds. This completes the proof of Theorem~\ref{nec}. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{$K_{3,m}$-free graphs}\label{sec3} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we prove Theorem~\ref{ns1}. We first show that $\G _{3}(\{K_{3},K_{3,m},Y_{3}\})$ and $\G _{3}(\{K_{3},K_{3,m},P_{5}\})$ are finite. \begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns1 prop1} Let $m\geq 4$. Then $\G _{3}(\{K_{3},K_{3,m},Y_{3}\})$ is finite. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $G\in \G _{3}(\{K_{3},K_{3,m},Y_{3}\})$. We show that $|V(G)|\leq (m+1)^{3}$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns1 prop1 cl1} $\mbox{diam}(G)\leq 3$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Suppose that $\mbox{diam}(G)\geq 4$. Let $x,y\in V(G)$ be vertices with $d(x,y)=4$, and let $x_{0}x_{1}\cdots x_{4}$ be a shortest $x$-$y$ path in $G$. Since $G$ is $3$-connected, $N(x_{2})-\{x_{1},x_{3}\}\not=\emptyset $. Let $z\in N(x_{2})-\{x_{1},x_{3}\}$. Since $G$ is $K_{3}$-free, $zx_{1},zx_{3}\not\in E(G)$. Since $d(x_{0},x_{4})=4$, $z$ is adjacent to at most one of $x_{0}$ and $x_{4}$. Hence $\{x_{0},x_{1},x_{2},x_{3},z\}$ or $\{x_{4},x_{3},x_{2},x_{1},z\}$ induces $Y_{3}$, which is a contradiction. \qed In view of Claim~\ref{ns1 prop1 cl1} and Lemma~\ref{new diam lem}, it suffices to show that $\Delta (G)\leq m+1$. Suppose that $\Delta (G)\geq m+2$. Let $w\in V(G)$ be a vertex such that $d(w)=\Delta (G)$, and let $x\in N(w)$. Since $G$ is $K_{3}$-free, both $N(w)$ and $N(x)$ are independent. Since $G$ is $3$-connected, $d(x)\geq 3$. Take $y_{1},y_{2}\in N(x)-\{w\}$. If $|N(w)-N(y_{i})|\geq 2$ for $i=1$ or $2$, say $a,b\in N(w)-N(y_{i})$, then $\{y_{i},x,w,a,b\}$ induces $Y_{3}$, a contradiction. Thus $|N(y_{i})\cap N(w)|\geq d(w)-1$ for each $i=1,2$. Consequently $|N(w)\cap N(y_{1})\cap N(y_{2})|\geq d(w)-2\geq m$, which implies that $G[\{w,y_{1},y_{2}\}\cup (N(w)\cap N(y_{1})\cap N(y_{2}))]$ contains $K_{3,m}$ as an induced subgraph, a contradiction. \qed \begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns1 prop2} Let $m\geq 4$. Then $\G _{3}(\{K_{3},K_{3,m},P_{5}\})$ is finite. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $G\in \G _{3}(\{K_{3},K_{3,m},P_{5}\})$. We show that $|V(G)|\leq (4m-1)^{3}$. Since $G$ is $P_{5}$-free, $\mbox{diam}(G)\leq 3$. Thus in view of Lemma~\ref{new diam lem}, it suffices to show that $\Delta (G)\leq 4m-1$. Suppose that $\Delta (G)\geq 4m$, and let $w\in V(G)$ be a vertex with $d(w)=\Delta (G)$. Since $G$ is $K_{3}$-free, $N(w)$ is an independent set. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns1 prop2 cl1} Let $X\subseteq N(w)$, and let $Y$ be a minimal subset of $N_{2}(w)$ such that $N(Y)\supseteq X$. Then $|Y|\leq 2$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Suppose that $|Y|\geq 3$. Since $G$ is $K_{3}$-free, there exist vertices $y_{1},y_{2}\in Y$ such that $y_{1}y_{2}\not\in E(G)$. By the minimality of $Y$, $(N(y_{i})\cap X)-N(y_{3-i})\not=\emptyset $ for each $i=1,2$. For $i=1,2$, let $x_{i}\in (N(y_{i})\cap X)-N(y_{3-i})$. Then $\{y_{1},x_{1},w,x_{2},y_{2}\}$ induces $P_{5}$, a contradiction. \qed Since $G$ is $3$-connected and $N(w)$ is independent, $N(N_{2}(w))\supseteq N(w)$. Let $Y$ be a minimal subset of $N_{2}(w)$ such that $N(Y)\supseteq N(w)$. Then $|Y|\leq 2$ by Claim~\ref{ns1 prop2 cl1}. Hence there exists $y\in Y$ such that $|N(w)\cap N(y)|\geq d(w)/2\geq 2m$. Since $G$ is $3$-connected and $N(w)$ is independent, $N(N_{2}(w)-\{y\})\supseteq N(w)\cap N(y)$. Let $Y^{*}$ be a minimal subset of $N_{2}(w)-\{y\}$ such that $N(Y^{*})\supseteq N(w)\cap N(y)$ (see Figure~\ref{f2}). Then $|Y^{*}|\leq 2$ by Claim~\ref{ns1 prop2 cl1}. Hence there exists $y'\in Y^{*}$ such that $|N(w)\cap N(y)\cap N(y')|\geq m$. Since $N(y)\cap N(y')\not=\emptyset $, we have $yy'\not\in E(G)$ by the assumption that $G$ is $K_{3}$-free. Consequently $G[\{w,y,y'\}\cup (N(w)\cap N(y)\cap N(y'))]$ contains $K_{3,m}$ as an induced subgraph, a contradiction. \qed \begin{figure} \begin{center} %WinTpicVersion4.10 \unitlength 0.1in \begin{picture}( 22.0000, 12.8500)( 3.0000,-15.3500) % CIRCLE 2 0 0 0 Black Black % 4 1400 1400 1400 1450 1400 1450 1400 1450 % \special{sh 1.000}% \special{ia 1400 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1400 1400 50 50 0.0000000 6.2831853}% % BOX 1 0 3 0 Black Black % 2 400 1200 2400 800 % \special{pn 13}% \special{pa 400 1200}% \special{pa 2400 1200}% \special{pa 2400 800}% \special{pa 400 800}% \special{pa 400 1200}% \special{pa 2400 1200}% \special{fp}% % BOX 1 0 3 0 Black Black % 2 500 1100 1500 900 % \special{pn 13}% \special{pa 500 1100}% \special{pa 1500 1100}% \special{pa 1500 900}% \special{pa 500 900}% \special{pa 500 1100}% \special{pa 1500 1100}% \special{fp}% % BOX 1 0 3 0 Black Black % 2 450 850 2050 1150 % \special{pn 13}% \special{pa 450 850}% \special{pa 2050 850}% \special{pa 2050 1150}% \special{pa 450 1150}% \special{pa 450 850}% \special{pa 2050 850}% \special{fp}% % BOX 1 0 3 0 Black Black % 2 1800 500 2400 300 % \special{pn 13}% \special{pa 1800 500}% \special{pa 2400 500}% \special{pa 2400 300}% \special{pa 1800 300}% \special{pa 1800 500}% \special{pa 2400 500}% \special{fp}% % BOX 1 0 3 0 Black Black % 2 300 250 2500 550 % \special{pn 13}% \special{pa 300 250}% \special{pa 2500 250}% \special{pa 2500 550}% \special{pa 300 550}% \special{pa 300 250}% \special{pa 2500 250}% \special{fp}% % CIRCLE 2 0 0 0 Black Black % 4 600 400 600 450 600 450 600 450 % \special{sh 1.000}% \special{ia 600 400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 600 400 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 8 600 400 500 900 1500 900 600 400 1400 1400 400 1200 2400 1200 1400 1400 % \special{pn 8}% \special{pa 600 400}% \special{pa 500 900}% \special{fp}% \special{pa 1500 900}% \special{pa 600 400}% \special{fp}% \special{pa 1400 1400}% \special{pa 400 1200}% \special{fp}% \special{pa 2400 1200}% \special{pa 1400 1400}% \special{fp}% % LINE 2 0 3 0 Black Black % 4 1800 500 450 850 2050 850 2400 500 % \special{pn 8}% \special{pa 1800 500}% \special{pa 450 850}% \special{fp}% \special{pa 2050 850}% \special{pa 2400 500}% \special{fp}% % STR 2 0 3 0 Black Black % 4 2750 300 2750 400 5 0 0 0 % $N_{2}(w)$ \put(27.5000,-4.0000){\makebox(0,0){$N_{2}(w)$}}% % STR 2 0 3 0 Black Black % 4 2650 900 2650 1000 5 0 0 0 % $N(w)$ \put(26.5000,-10.0000){\makebox(0,0){$N(w)$}}% % STR 2 0 3 0 Black Black % 4 1400 1500 1400 1600 5 0 0 0 % $w$ \put(14.0000,-16.0000){\makebox(0,0){$w$}}% % STR 2 0 3 0 Black Black % 4 430 300 430 400 5 0 0 0 % $y$ \put(4.3000,-4.0000){\makebox(0,0){$y$}}% % STR 2 0 3 0 Black Black % 4 2100 300 2100 400 5 0 0 0 % $Y^{*}$ \put(21.0000,-4.0000){\makebox(0,0){$Y^{*}$}}% \end{picture}% \caption{Vertex $y$ and set $Y^{*}$} \label{f2} \end{center} \end{figure} \medbreak\noindent\textit{Proof of Theorem~\ref{ns1}.}\quad The `if' part follows from Propositions~\ref{ns1 prop1} and \ref{ns1 prop2}. Thus it suffices to prove the `only if' part. Suppose that $\G _{3}(\{K_{3},K_{3,m},T\})$ is finite. From Theorem~\ref{nec}, it follows that $T\in \T _{2}$. For each $s\geq 2$, let $H_{s}$ be the graph defined by $V(H_{s})=\{x_{i,j}\mid 1\leq i,j\leq 2\}\cup \{y_{i,j}\mid 1\leq i\leq 2,1\leq j\leq s\}$ and $E(H_{s})=\{x_{1,j}x_{2,h}\mid 1\leq j,h\leq 2\}\cup \{x_{i,j}y_{i,h}\mid 1\leq i,j\leq 2,1\leq h\leq s\}\cup \{y_{1,j}y_{2,j}\mid 1\leq j\leq s\}$. Then $H_{s}$ is $3$-connected and $\{K_{3},K_{3,m}\}$-free since $m\geq 4$. Since $\G _{3}(\{K_{3},K_{3,m},T\})$ is finite, there exists $s\geq 2$ such that $H_{s}$ contains $T$ as an induced subgraph. By inspection, we see that if $F$ is a member of $\T _{2}$ contained in $H_{s}$ as an induced subgraph, then $F$ is a path of order $4$ or $5$ or $F=Y_{3}$. Hence $T$ is a path of order $4$ or $5$ or $T=Y_{3}$. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{$\{K_{4},K_{2,m}\}$-free graphs}\label{sec4} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we prove Theorem~\ref{ns2}. \begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns2 prop1} Let $m\geq 3$. Then $\G _{3}(\{K_{4},K_{2,m},P_{5}\})$ is finite. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof By part (i) of Theorem~\ref{tri 2-conn}, there exists a positive integer $t=t(m)$ such that every $2$-connected $\{K_{3},K_{2,m},P_{5}\}$-free graph has order at most $t$. Let $G\in \G _{3}(\{K_{4},K_{2,m},P_{5}\})$. We show that $|V(G)|\leq (3(3m-1)t/2)^{3}$. Note that $\mbox{diam}(G)\leq 3$. Thus in view of Lemma~\ref{new diam lem}, it suffices to show that $\Delta (G)\leq 3(3m-1)t/2$. Suppose that $\Delta (G)>3(3m-1)t/2$, and let $w\in V(G)$ be a vertex with $d(w)=\Delta (G)$. Since $G$ is $\{K_{4},K_{2,m},P_{5}\}$-free, $G[N(w)]$ is $\{K_{3},K_{2,m},P_{5}\}$-free. Let $F$ be a component of $G[N(w)]$. If $F$ has two or more blocks which are not endblocks, then $F$ contains $P_{5}$ as an induced subgraph, a contradiction. Thus $F$ has at most one block which is not an endblock, which implies that at least two thirds of the blocks of $F$ are endblocks. Since $F$ is arbitrary, it follows that at least two thirds of the blocks of $G[N(w)]$ are endblocks. Now suppose that $G[N(w)]$ has at most $3m-1$ endblocks. Then $G[N(w)]$ has at most $3(3m-1)/2$ blocks. Since $d(w)>3(3m-1)t/2$, it follows that there exists a block $B$ of $G[N(w)]$ with $|V(B)|>t$. Since $G[N(w)]$ is $\{K_{3},K_{2,m},P_{5}\}$-free, this contradicts the definition of $t$. Thus $G[N(w)]$ has at least $3m$ endblocks. Let $B_{1},\ldots ,B_{3m}$ be endblocks of $G[N(w)]$. Since $G$ is $3$-connected, we see that for each $1\leq i\leq 3m$, there exists an internal vertex $x_{i}$ of $B_{i}$ such that $N(x_{i})\cap (V(G)-(\{w\}\cup N(w)))\not=\emptyset $ (see Figure~\ref{f3}). Set $X=\{x_{1},\ldots ,x_{3m}\}$. Then $X$ is an independent set of $G$, and we have $N(N_{2}(w))\supseteq X$. Let $Y$ be a minimal subset of $N_{2}(w)$ such that $N(Y)\supseteq X$. If $|Y|\leq 3$, then there exists $y\in Y$ such that $|N(y)\cap X|\geq m$, and hence $G[\{w,y\}\cup (N(y)\cap X)]$ contains $K_{2,m}$ as an induced subgraph, a contradiction. Thus $|Y|\geq 4$. Since $G$ is $K_{4}$-free, there exist vertices $y_{1},y_{2}\in Y$ such that $y_{1}y_{2}\not\in E(G)$. By the minimality of $Y$, $(N(y_{i})\cap X)-N(y_{3-i})\not=\emptyset $ for each $i=1,2$. For $i=1,2$, let $x'_{i}\in (N(y_{i})\cap X)-N(y_{3-i})$. Then $\{y_{1},x'_{1},w,x'_{2},y_{2}\}$ induces $P_{5}$, a contradiction. \qed \begin{figure} \begin{center} %WinTpicVersion4.10 \unitlength 0.1in \begin{picture}( 32.7500, 15.8500)( 4.0000,-24.8500) % CIRCLE 2 0 0 0 Black Black % 4 2000 2400 2050 2400 2050 2400 2050 2400 % \special{sh 1.000}% \special{ia 2000 2400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2000 2400 50 50 0.0000000 6.2831853}% % ELLIPSE 2 0 3 0 Black White % 4 800 1800 1100 2000 1100 2000 1100 2000 % \special{pn 8}% \special{ar 800 1800 300 200 0.0000000 6.2831853}% % ELLIPSE 2 0 3 0 Black White % 4 1700 1800 2000 2000 2000 2000 2000 2000 % \special{pn 8}% \special{ar 1700 1800 300 200 0.0000000 6.2831853}% % ELLIPSE 2 0 3 0 Black White % 4 2500 1800 2800 2000 2800 2000 2800 2000 % \special{pn 8}% \special{ar 2500 1800 300 200 0.0000000 6.2831853}% % DOT 0 0 3 0 Black Black % 5 3100 1800 3300 1800 3200 1800 3200 1800 3200 1800 % \special{pn 4}% \special{sh 1}% \special{ar 3100 1800 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 3300 1800 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 3200 1800 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 3200 1800 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 3200 1800 14 14 0 6.28318530717959E+0000}% % CIRCLE 2 0 0 0 Black Black % 4 800 1690 850 1690 850 1690 850 1690 % \special{sh 1.000}% \special{ia 800 1690 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 800 1690 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1700 1690 1750 1690 1750 1690 1750 1690 % \special{sh 1.000}% \special{ia 1700 1690 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1700 1690 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2500 1690 2550 1690 2550 1690 2550 1690 % \special{sh 1.000}% \special{ia 2500 1690 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2500 1690 50 50 0.0000000 6.2831853}% % STR 2 0 3 0 Black Black % 4 800 1740 800 1840 5 0 0 0 % $x_{1}$ \put(8.0000,-18.4000){\makebox(0,0){$x_{1}$}}% % STR 2 0 3 0 Black Black % 4 1700 1740 1700 1840 5 0 0 0 % $x_{2}$ \put(17.0000,-18.4000){\makebox(0,0){$x_{2}$}}% % STR 2 0 3 0 Black Black % 4 2510 1740 2510 1840 5 0 0 0 % $x_{3}$ \put(25.1000,-18.4000){\makebox(0,0){$x_{3}$}}% % STR 2 0 3 0 Black White % 4 1150 1900 1150 2000 5 0 0 0 % $B_{1}$ \put(11.5000,-20.0000){\makebox(0,0){$B_{1}$}}% % STR 2 0 3 0 Black White % 4 2050 1900 2050 2000 5 0 0 0 % $B_{2}$ \put(20.5000,-20.0000){\makebox(0,0){$B_{2}$}}% % STR 2 0 3 0 Black White % 4 2910 1900 2910 2000 5 0 0 0 % $B_{3}$ \put(29.1000,-20.0000){\makebox(0,0){$B_{3}$}}% % BOX 1 0 3 0 Black Black % 2 400 1500 3600 2100 % \special{pn 13}% \special{pa 400 1500}% \special{pa 3600 1500}% \special{pa 3600 2100}% \special{pa 400 2100}% \special{pa 400 1500}% \special{pa 3600 1500}% \special{fp}% % BOX 1 0 3 0 Black Black % 2 400 1300 3600 900 % \special{pn 13}% \special{pa 400 1300}% \special{pa 3600 1300}% \special{pa 3600 900}% \special{pa 400 900}% \special{pa 400 1300}% \special{pa 3600 1300}% \special{fp}% % STR 2 0 3 0 Black Black % 4 3850 1000 3850 1100 5 0 0 0 % $N_{2}(w)$ \put(38.5000,-11.0000){\makebox(0,0){$N_{2}(w)$}}% % STR 2 0 3 0 Black Black % 4 3850 1700 3850 1800 5 0 0 0 % $N(w)$ \put(38.5000,-18.0000){\makebox(0,0){$N(w)$}}% % LINE 2 0 3 0 Black Black % 4 2000 2400 400 2100 3600 2100 2000 2400 % \special{pn 8}% \special{pa 2000 2400}% \special{pa 400 2100}% \special{fp}% \special{pa 3600 2100}% \special{pa 2000 2400}% \special{fp}% % STR 2 0 3 0 Black Black % 4 2000 2450 2000 2550 5 0 0 0 % $w$ \put(20.0000,-25.5000){\makebox(0,0){$w$}}% % ELLIPSE 2 0 3 0 Black White % 4 1250 1810 1400 1920 1400 1920 1400 1920 % \special{pn 8}% \special{ar 1250 1810 150 110 0.0000000 6.2831853}% % DOT 2 0 3 0 Black White % 1 1400 1810 % \special{pn 4}% \special{sh 1}% \special{ar 1400 1810 6 6 0 6.28318530717959E+0000}% % CIRCLE 2 0 0 0 Black Black % 4 1390 1810 1420 1810 1420 1810 1420 1810 % \special{sh 1.000}% \special{ia 1390 1810 30 30 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1390 1810 30 30 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1100 1810 1130 1810 1130 1810 1130 1810 % \special{sh 1.000}% \special{ia 1100 1810 30 30 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1100 1810 30 30 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 6 800 1700 1000 1100 1700 1690 1610 1090 2500 1690 2300 1090 % \special{pn 8}% \special{pa 800 1700}% \special{pa 1000 1100}% \special{fp}% \special{pa 1700 1690}% \special{pa 1610 1090}% \special{fp}% \special{pa 2500 1690}% \special{pa 2300 1090}% \special{fp}% \end{picture}% \caption{Endblocks $B_{i}$ and vertices $x_{i}$} \label{f3} \end{center} \end{figure} \medbreak\noindent\textit{Proof of Theorem~\ref{ns2}.}\quad The `if' part follows from Proposition~\ref{ns2 prop1}. Thus it suffices to prove the `only if' part. Suppose that $\G _{3}(\{K_{4},K_{2,m},T\})$ is finite. From Theorem~\ref{nec}, it follows that $T$ is a path. For each $s\geq 2$, let $H_{s}$ be the graph defined by $V(H_{s})=\{x_{i},y_{i,j}\mid 1\leq i\leq 3,1\leq j\leq s\}$ and $E(H_{s})=\{x_{i}x_{j},y_{i,h}y_{j,h}\mid i\not=j,1\leq h\leq s\}\cup \{x_{i}y_{j,h}\mid i\not=j,1\leq h\leq s\}$ (see Figure~\ref{f6}). Then $H_{s}$ is $3$-connected and $\{K_{4},K_{2,m}\}$-free. Hence there exists $s\geq 2$ such that $H_{s}$ contains $T$ as an induced subgraph. Since every induced path of $H_{s}$ has order at most $5$, $T$ has order at most $5$. Since $T\not=K_{1,2}$ by assumption, it follows that $T$ is a path of order $4$ or $5$. \qed \begin{figure} \begin{center} %WinTpicVersion4.10 \unitlength 0.1in \begin{picture}( 35.0000, 15.7500)( 3.5000,-23.3500) % CIRCLE 2 0 0 0 Black Black % 4 600 1000 650 1000 650 1000 650 1000 % \special{sh 1.000}% \special{ia 600 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 600 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1000 1000 1050 1000 1050 1000 1050 1000 % \special{sh 1.000}% \special{ia 1000 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1000 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1400 1000 1450 1000 1450 1000 1450 1000 % \special{sh 1.000}% \special{ia 1400 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1400 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1800 2200 1850 2200 1850 2200 1850 2200 % \special{sh 1.000}% \special{ia 1800 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1800 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2200 2200 2250 2200 2250 2200 2250 2200 % \special{sh 1.000}% \special{ia 2200 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2200 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2600 2200 2650 2200 2650 2200 2650 2200 % \special{sh 1.000}% \special{ia 2600 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2600 2200 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 2 2600 2200 1800 2200 % \special{pn 8}% \special{pa 2600 2200}% \special{pa 1800 2200}% \special{fp}% % SPLINE 2 0 3 0 Black Black % 4 1800 2200 2200 2000 2600 2200 2600 2200 % \special{pn 8}% \special{pa 1800 2200}% \special{pa 1830 2180}% \special{pa 1858 2158}% \special{pa 1886 2138}% \special{pa 1914 2116}% \special{pa 1944 2098}% \special{pa 1972 2080}% \special{pa 2000 2062}% \special{pa 2030 2048}% \special{pa 2058 2034}% \special{pa 2086 2022}% \special{pa 2116 2014}% \special{pa 2144 2006}% \special{pa 2172 2002}% \special{pa 2202 2000}% \special{pa 2230 2002}% \special{pa 2258 2006}% \special{pa 2288 2014}% \special{pa 2316 2022}% \special{pa 2344 2034}% \special{pa 2372 2048}% \special{pa 2402 2064}% \special{pa 2430 2080}% \special{pa 2458 2098}% \special{pa 2488 2118}% \special{pa 2516 2138}% \special{pa 2544 2158}% \special{pa 2574 2180}% \special{pa 2600 2200}% \special{sp}% % LINE 2 0 3 0 Black Black % 2 600 1000 1400 1000 % \special{pn 8}% \special{pa 600 1000}% \special{pa 1400 1000}% \special{fp}% % SPLINE 2 0 3 0 Black Black % 4 1400 1000 1000 1200 600 1000 600 1000 % \special{pn 8}% \special{pa 1400 1000}% \special{pa 1372 1022}% \special{pa 1344 1044}% \special{pa 1314 1064}% \special{pa 1286 1084}% \special{pa 1258 1104}% \special{pa 1228 1122}% \special{pa 1200 1138}% \special{pa 1172 1154}% \special{pa 1142 1166}% \special{pa 1114 1178}% \special{pa 1086 1188}% \special{pa 1058 1194}% \special{pa 1028 1200}% \special{pa 1000 1200}% \special{pa 972 1198}% \special{pa 942 1194}% \special{pa 914 1188}% \special{pa 886 1178}% \special{pa 856 1166}% \special{pa 828 1152}% \special{pa 800 1138}% \special{pa 770 1120}% \special{pa 742 1102}% \special{pa 714 1084}% \special{pa 684 1062}% \special{pa 656 1042}% \special{pa 628 1020}% \special{pa 600 1000}% \special{sp}% % CIRCLE 2 0 0 0 Black Black % 4 1600 1000 1650 1000 1650 1000 1650 1000 % \special{sh 1.000}% \special{ia 1600 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1600 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2000 1000 2050 1000 2050 1000 2050 1000 % \special{sh 1.000}% \special{ia 2000 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2000 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2400 1000 2450 1000 2450 1000 2450 1000 % \special{sh 1.000}% \special{ia 2400 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2400 1000 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 2 1600 1000 2400 1000 % \special{pn 8}% \special{pa 1600 1000}% \special{pa 2400 1000}% \special{fp}% % SPLINE 2 0 3 0 Black Black % 4 2400 1000 2000 1200 1600 1000 1600 1000 % \special{pn 8}% \special{pa 2400 1000}% \special{pa 2372 1022}% \special{pa 2344 1044}% \special{pa 2314 1064}% \special{pa 2286 1084}% \special{pa 2258 1104}% \special{pa 2228 1122}% \special{pa 2200 1138}% \special{pa 2172 1154}% \special{pa 2142 1166}% \special{pa 2114 1178}% \special{pa 2086 1188}% \special{pa 2058 1194}% \special{pa 2028 1200}% \special{pa 2000 1200}% \special{pa 1972 1198}% \special{pa 1942 1194}% \special{pa 1914 1188}% \special{pa 1886 1178}% \special{pa 1856 1166}% \special{pa 1828 1152}% \special{pa 1800 1138}% \special{pa 1770 1120}% \special{pa 1742 1102}% \special{pa 1714 1084}% \special{pa 1684 1062}% \special{pa 1656 1042}% \special{pa 1628 1020}% \special{pa 1600 1000}% \special{sp}% % CIRCLE 2 0 0 0 Black Black % 4 3000 1000 3050 1000 3050 1000 3050 1000 % \special{sh 1.000}% \special{ia 3000 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3000 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3400 1000 3450 1000 3450 1000 3450 1000 % \special{sh 1.000}% \special{ia 3400 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3400 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3800 1000 3850 1000 3850 1000 3850 1000 % \special{sh 1.000}% \special{ia 3800 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3800 1000 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 2 3000 1000 3800 1000 % \special{pn 8}% \special{pa 3000 1000}% \special{pa 3800 1000}% \special{fp}% % SPLINE 2 0 3 0 Black Black % 4 3800 1000 3400 1200 3000 1000 3000 1000 % \special{pn 8}% \special{pa 3800 1000}% \special{pa 3772 1022}% \special{pa 3744 1044}% \special{pa 3714 1064}% \special{pa 3686 1084}% \special{pa 3658 1104}% \special{pa 3628 1122}% \special{pa 3600 1138}% \special{pa 3572 1154}% \special{pa 3542 1166}% \special{pa 3514 1178}% \special{pa 3486 1188}% \special{pa 3458 1194}% \special{pa 3428 1200}% \special{pa 3400 1200}% \special{pa 3372 1198}% \special{pa 3342 1194}% \special{pa 3314 1188}% \special{pa 3286 1178}% \special{pa 3256 1166}% \special{pa 3228 1152}% \special{pa 3200 1138}% \special{pa 3170 1120}% \special{pa 3142 1102}% \special{pa 3114 1084}% \special{pa 3084 1062}% \special{pa 3056 1042}% \special{pa 3028 1020}% \special{pa 3000 1000}% \special{sp}% % LINE 2 0 3 0 Black Black % 12 1800 2200 1000 1000 1800 2200 1400 1000 2000 1000 1800 2200 1800 2200 2400 1000 3400 1000 1800 2200 1800 2200 3800 1000 % \special{pn 8}% \special{pa 1800 2200}% \special{pa 1000 1000}% \special{fp}% \special{pa 1800 2200}% \special{pa 1400 1000}% \special{fp}% \special{pa 2000 1000}% \special{pa 1800 2200}% \special{fp}% \special{pa 1800 2200}% \special{pa 2400 1000}% \special{fp}% \special{pa 3400 1000}% \special{pa 1800 2200}% \special{fp}% \special{pa 1800 2200}% \special{pa 3800 1000}% \special{fp}% % LINE 2 0 3 0 Black Black % 24 2200 2200 600 1000 1400 1000 2200 2200 2200 2200 1600 1000 2400 1000 2200 2200 2200 2200 3000 1000 3800 1000 2200 2200 2600 2200 600 1000 1000 1000 2600 2200 2600 2200 1600 1000 2000 1000 2600 2200 2600 2200 3000 1000 3400 1000 2600 2200 % \special{pn 8}% \special{pa 2200 2200}% \special{pa 600 1000}% \special{fp}% \special{pa 1400 1000}% \special{pa 2200 2200}% \special{fp}% \special{pa 2200 2200}% \special{pa 1600 1000}% \special{fp}% \special{pa 2400 1000}% \special{pa 2200 2200}% \special{fp}% \special{pa 2200 2200}% \special{pa 3000 1000}% \special{fp}% \special{pa 3800 1000}% \special{pa 2200 2200}% \special{fp}% \special{pa 2600 2200}% \special{pa 600 1000}% \special{fp}% \special{pa 1000 1000}% \special{pa 2600 2200}% \special{fp}% \special{pa 2600 2200}% \special{pa 1600 1000}% \special{fp}% \special{pa 2000 1000}% \special{pa 2600 2200}% \special{fp}% \special{pa 2600 2200}% \special{pa 3000 1000}% \special{fp}% \special{pa 3400 1000}% \special{pa 2600 2200}% \special{fp}% % DOT 0 0 3 0 Black Black % 4 2600 1000 2800 1000 2700 1000 2700 1000 % \special{pn 4}% \special{sh 1}% \special{ar 2600 1000 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 2800 1000 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 2700 1000 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 2700 1000 14 14 0 6.28318530717959E+0000}% % STR 2 0 3 0 Black Black % 4 1800 2300 1800 2400 5 0 0 0 % $x_{1}$ \put(18.0000,-24.0000){\makebox(0,0){$x_{1}$}}% % STR 2 0 3 0 Black Black % 4 2200 2300 2200 2400 5 0 0 0 % $x_{2}$ \put(22.0000,-24.0000){\makebox(0,0){$x_{2}$}}% % STR 2 0 3 0 Black Black % 4 2600 2300 2600 2400 5 0 0 0 % $x_{3}$ \put(26.0000,-24.0000){\makebox(0,0){$x_{3}$}}% % STR 2 0 3 0 Black Black % 4 600 725 600 825 5 0 0 0 % $y_{1,1}$ \put(6.0000,-8.2500){\makebox(0,0){$y_{1,1}$}}% % STR 2 0 3 0 Black Black % 4 1000 725 1000 825 5 0 0 0 % $y_{2,1}$ \put(10.0000,-8.2500){\makebox(0,0){$y_{2,1}$}}% % STR 2 0 3 0 Black Black % 4 1350 725 1350 825 5 0 0 0 % $y_{3,1}$ \put(13.5000,-8.2500){\makebox(0,0){$y_{3,1}$}}% % STR 2 0 3 0 Black Black % 4 1650 725 1650 825 5 0 0 0 % $y_{1,2}$ \put(16.5000,-8.2500){\makebox(0,0){$y_{1,2}$}}% % STR 2 0 3 0 Black Black % 4 2000 725 2000 825 5 0 0 0 % $y_{2,2}$ \put(20.0000,-8.2500){\makebox(0,0){$y_{2,2}$}}% % STR 2 0 3 0 Black Black % 4 2400 725 2400 825 5 0 0 0 % $y_{3,2}$ \put(24.0000,-8.2500){\makebox(0,0){$y_{3,2}$}}% % STR 2 0 3 0 Black Black % 4 3000 725 3000 825 5 0 0 0 % $y_{1,s}$ \put(30.0000,-8.2500){\makebox(0,0){$y_{1,s}$}}% % STR 2 0 3 0 Black Black % 4 3400 725 3400 825 5 0 0 0 % $y_{2,s}$ \put(34.0000,-8.2500){\makebox(0,0){$y_{2,s}$}}% % STR 2 0 3 0 Black Black % 4 3800 725 3800 825 5 0 0 0 % $y_{3,s}$ \put(38.0000,-8.2500){\makebox(0,0){$y_{3,s}$}}% \end{picture}% \caption{Graph $H_{s}$} \label{f6} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{$K_{1,m}$-free graphs}\label{sec5} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we prove Theorem~\ref{ns4}. We first prove a lemma, which we also use in Section~\ref{sec6}. \begin{lem}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns4 lem1} Let $n\geq 3$, and let $G$ be a $3$-connected $\{K_{3},Y^{*}_{n}\}$-free graph. If $n=3$, let $t(n)=7$; if $n\geq 4$, let $t(n)=3n+10$. Then $\mbox{diam}(G)\leq t(n)$. In particular, $\mbox{diam}(G)\leq 3n+10$. \end{lem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $t=t(n)$, and suppose that $\mbox{diam}(G)\geq t+1$. Let $x,y\in V(G)$ be vertices such that $d(x,y)=t+1$, and let $P=x_{0}x_{1}\cdots x_{t+1}$ be a shortest $x$-$y$ path in $G$. Since $G$ is $3$-connected, $N(x_{i})-\{x_{i-1},x_{i+1}\}\not=\emptyset $ for each $1\leq i\leq t$. Let $x'_{i}\in N(x_{i})-\{x_{i-1},x_{i+1}\}$. \medskip \noindent \textbf{Case 1:} $n=3$ We first show that $N(x_{3})\cap N(x_{5})=\{x_{4}\}$. By way of contradiction, suppose that $|N(x_{3})\cap N(x_{5})|\geq 2$. Then we may assume we have chosen $x'_{3}$ and $x'_{5}$ so that $x'_{3}=x'_{5}\in (N(x_{3})\cap N(x_{5}))-\{x_{4}\}$. Since $d(x_{0},x_{8})=8$ and $G$ is $K_{3}$-free, we get $N(x'_{3})\cap V(P)=\{x_{3},x_{5}\}$, $N(x'_{1})\cap V(P)\subseteq \{x_{1},x_{3}\}$, $N(x'_{7})\cap V(P)\subseteq \{x_{5},x_{7}\}$, and $x'_{1}x'_{3},x'_{3}x'_{7}\not\in E(G)$. Since neither $\{x_{0},x'_{1},x_{1},x_{2},x_{3},x_{4},x'_{3}\}$ nor $\{x_{4},x'_{3},x_{5},x_{6},x_{7},x_{8},x'_{7}\}$ induces $Y^{*}_{3}$, this forces $N(x'_{1})\cap V(P)=\{x_{1},x_{3}\}$ and $N(x'_{7})\cap V(P)=\{x_{5},x_{7}\}$. But then $\{x_{2},x'_{1},x_{3},x_{4},x_{5},x_{6},x'_{7}\}$ induces $Y^{*}_{3}$, a contradiction. Thus $N(x_{3})\cap N(x_{5})=\{x_{4}\}$. Choose $z\in N(x_{3})-\{x_{2},x_{4}\}$. Since $\{x_{2},z,x_{3},x_{4},x_{5},x_{6},x'_{5}\}$ does not induce $Y^{*}_{3}$ and $N(x_{3})\cap N(x_{5})=\{x_{4}\}$, we get $zx'_{5}\in E(G)$. Since $d(x_{1},x_{5})=4$, it follows that $x_{1}z\not\in E(G)$. Since $z\in N(x_{3})-\{x_{2},x_{4}\}$ is arbitrary, this implies $N(x_{1})\cap N(x_{3})=\{x_{2}\}$; in particular, $x'_{1}x_{3}\not\in E(G)$. Letting $z=x'_{3}$, we also get $x'_{3}x'_{5}\in E(G)$ and $x_{1}x'_{3}\not\in E(G)$. Since $\{x_{0},x'_{1},x_{1},x_{2},x_{3},x_{4},x'_{3}\}$ does not induce $Y^{*}_{3}$, we now obtain $x'_{1}x'_{3}\in E(G)$. Similarly, $x'_{7}x'_{5}\in E(G)$. But then $x_{0}x_{1}x'_{1}x'_{3}x'_{5}x'_{7}x_{7}x_{8}$ is an $x_{0}$-$x_{8}$ path of length $7$, which contradicts the fact that $d(x_{0},x_{8})=8$. \medskip \noindent \textbf{Case 2:} $n\geq 4$ \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns4 lem1 cl1} For $0\leq i\leq t-n-1$, if $|N(x_{i})\cap N(x_{i+2})|\geq 2$, then $x'_{i+n+1}x_{i+n-1}\in E(G)$. For $n\leq i\leq t-1$, if $|N(x_{i})\cap N(x_{i+2})|\geq 2$, then $x'_{i-n+1}x_{i-n+3}\in E(G)$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $0\leq i\leq t-n-1$, and assume that $|N(x_{i})\cap N(x_{i+2})|\geq 2$. Let $u\in (N(x_{i})\cap N(x_{i+2}))-\{x_{i+1}\}$. Since $d(x_{0},x_{t+1})=t+1$ and $G$ is $K_{3}$-free, we have $N(u)\cap V(P)=\{x_{i},x_{i+2}\}$, $N(x'_{i+n+1})\cap \{x_{0},x_{1},\ldots ,x_{i+n+2}\}\subseteq \{x_{i+n-1},x_{i+n+1}\}$ and $ux'_{i+n+1}\not\in E(G)$. Since $\{x_{i+1},u,x_{i+2},\ldots ,x_{i+n+1},x_{i+n+2},x'_{i+n+1}\}$ does not induce $Y^{*}_{n}$, this implies $x'_{i+n+1}x_{i+n-1}\in E(G)$. Thus the first assertion is proved. We can similarly verify the second assertion. \qed \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns4 lem1 cl2} There is no integer $i$ with $n\leq i\leq t-n-2$ such that $|N(x_{i})\cap N(x_{i+2})|\geq 2$ and $|N(x_{i+1})\cap N(x_{i+3})|\geq 2$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Suppose that there exists an integer $i$ with $n\leq i\leq t-n-2$ such that $|N(x_{i})\cap N(x_{i+2})|\geq 2$ and $|N(x_{i+1})\cap N(x_{i+3})|\geq 2$. Then by Claim~\ref{ns4 lem1 cl1}, $x'_{i-n+1}x_{i-n+3},x'_{i+n+2}x_{i+n}\in E(G)$. This implies $|N(x_{i-n+1})\cap N(x_{i-n+3})|\geq 2$ and $|N(x_{i+n})\cap N(x_{i+n+2})|\geq 2$. Let $\mathcal{Q}$ be the set of $x_{i}$-$x_{i+3}$ paths of order $4$, and let $X=(\bigcup_{Q\in \mathcal{Q}}V(Q))-\{x_{i},x_{i+3}\}$. Since $G-\{x_{i},x_{i+3}\}$ is connected and $V(G)-(X\cup \{x_{i},x_{i+3}\})\not=\emptyset $, there exists $z\in X$ such that $N(z)-(X\cup \{x_{i},x_{i+3}\})\not=\emptyset $. By the definition of $X$, $z$ is adjacent to $x_{i}$ or $x_{i+3}$. By symmetry, we may assume $zx_{i}\in E(G)$. Then there exists $z'\in X$ such that $x_{i}zz'x_{i+3}$ is an $x_{i}$-$x_{i+3}$ path. Now take $w\in N(z)-(X\cup \{x_{i},x_{i+3}\})$. Since $|N(x_{i+n})\cap N(x_{i+n+2})|\geq 2$, we obtain $wx_{i+3}\in E(G)$ by applying the second assertion of Claim~\ref{ns4 lem1 cl1} to the path $x_{0}x_{1}\cdots x_{i}zz'x_{i+3}x_{i+4}\cdots x_{t+1}$. But then $x_{i}zwx_{i+3}\in \mathcal{Q}$, which contradicts the fact that $w\not\in X$. \qed \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns4 lem1 cl3} For $n+2\leq i\leq t-2n$, we have $x'_{i-1}x'_{i+n-2}\in E(G)$ or $x'_{i}x'_{i+n-1}\in E(G)$ or $x'_{i+1}x'_{i+n}\in E(G)$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Suppose that $x'_{i}x'_{i+n-1}\not\in E(G)$. Since $\{x_{i-1},x'_{i},x_{i},\ldots ,x_{i+n-1},x_{i+n},x'_{i+n-1}\}$ does not induce $Y^{*}_{n}$, $x'_{i}x_{i+2}\in E(G)$ or $x'_{i+n-1}x_{i+n-3}\in E(G)$. First assume that $x'_{i}x_{i+2}\in E(G)$. Since $0\leq i\leq t-n-1$, we have $x'_{i+n+1}x_{i+n-1}\in E(G)$ by Claim~\ref{ns4 lem1 cl1}. Since $n\leq i\leq t-n-2$ and $n\leq i+n-2\leq t-n-2$, $x'_{i+1}x_{i+3},x'_{i+n}x_{i+n-2}\not\in E(G)$ by Claim~\ref{ns4 lem1 cl2}. Since $\{x_{i},x'_{i+1},x_{i+1},\ldots ,x_{i+n},x_{i+n+1},x'_{i+n}\}$ does not induce $Y^{*}_{n}$ and $G$ is $K_{3}$-free, it follows that $x'_{i+1}x'_{i+n}\in E(G)$, as desired. Next assume that $x'_{i+n-1}x_{i+n-3}\in E(G)$. Arguing as above, we get $x'_{i-2}x_{i}\in E(G)$ by Claim~\ref{ns4 lem1 cl1}, and $x'_{i-1}x_{i+1},x'_{i+n-2}x_{i+n-4}\not\in E(G)$ by Claim~\ref{ns4 lem1 cl2}. Since $\{x_{i-2},x'_{i-1},x_{i-1},\ldots ,x_{i+n-2},x_{i+n-1},x'_{i+n-2}\}$ does not induce $Y^{*}_{n}$ and $G$ is $K_{3}$-free, it follows that $x'_{i-1}x'_{i+n-2}\in E(G)$, as desired. \qed Let $j=n+2$. Since $t\geq 3n+10$, we have $n+2\leq j\leq t-2n$. Hence it follows from Claim~\ref{ns4 lem1 cl3} that $x'_{j-1}x'_{j+n-2}\in E(G)$ or $x'_{j}x'_{j+n-1}\in E(G)$ or $x'_{j+1}x'_{j+n}\in E(G)$. Since $d(x_{j-1},x_{j+n-2})=d(x_{j},x_{j+n-1})=d(x_{j+1},x_{j+n})=n-1$, this forces $n=4$, and hence $t=22$ and $j=6$. In particular, $x'_{5}x'_{8}\in E(G)$ or $x'_{6}x'_{9}\in E(G)$ or $x'_{7}x'_{10}\in E(G)$. Let $s\in \{5,6,7\}$ be an integer such that $x'_{s}x'_{s+3}\in E(G)$. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns4 lem1 cl4} For $4\leq i\leq 11$, if $x'_{i}x'_{i+3}\in E(G)$, then $x'_{i+2}x'_{i+5}\in E(G)$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof If $x'_{i+3}x'_{i+6}\in E(G)$, then $x_{i}x'_{i}x'_{i+3}x'_{i+6}x_{i+6}$ is a path, which contradicts the fact that $d(x_{i},x_{i+6})=6$. Thus $x'_{i+3}x'_{i+6}\not\in E(G)$. Suppose that $x'_{i+2}x'_{i+5}\not\in E(G)$. Then $x'_{i+2}x'_{i+5},x'_{i+3}x'_{i+6}\not\in E(G)$. Since $n+2=6\leq i+2(m-1)^{2}$, $|U_{A_{0}}|\geq m$. Since $|B|\geq 2(m-1)^{7}-m+1>(m-1)^{2}$, $|V_{B}|\geq m$ by Claim~\ref{ns3 lem4 cl1}. Since $G$ is $K_{3}$-free, it follows that if both $c_{1}$ and $c_{2}$ are adjacent to all vertices in $V_{B}$, then $G[\{c_{1},c_{2}\}\cup V_{B}]$ contains $K_{2,m}$ as an induced subgraph, a contradiction. Thus $c_{h}v_{y}\not\in E(G)$ for some $h\in \{1,2\}$ and some $y\in B$. Then since $v_{y}\not\in N(a)\cup N(b)$, $ac_{h}byv_{y}$ is an induced path. Note that $U_{A_{0}}\subseteq N(w)$. Since $G$ is $K_{2,m}$-free, $|N(c_{h})\cap U_{A_{0}}|\leq |N(c_{h})\cap N(w)|\leq m-1$. Since $|U_{A_{0}}|\geq m$, there exists $x\in A_{0}$ such that $u_{x}c_{h}\not\in E(G)$. Then $u_{x}xac_{h}b$ is an induced path. Since $N(a)\cup N(b)$ is independent, $xy\not\in E(G)$. Since $k=3$, we also have $u_{x}y,xv_{y},u_{x}v_{y}\not\in E(G)$. Consequently the path $u_{x}xac_{h}byv_{y}$ is an induced path of order $7$, a contradiction. \medskip \noindent \textbf{Subcase 1.2:} $A_{1}\not=\emptyset $ and $B_{1}\not=\emptyset $ Let $x\in A_{1}$ and $y\in B_{1}$. Then since $u_{x},v_{y}\not\in N(a)\cup N(b)\cup N(w)$ and $k=3$, $u_{x}xawbyv_{y}$ is an induced path of order $7$, a contradiction. \medskip \noindent \textbf{Case 2:} $k=4$ Let $H_{1},\ldots ,H_{p}$ be the components of $G[A\cup B]$. Let $1\leq i\leq p$. Suppose that there exists $x\in V(H_{i})$ such that $d_{H_{i}}(x)\geq m$. We may assume that $x\in A$. Then $N_{H_{i}}(x)\subseteq B$, which implies that $G[\{b\}\cup V(H_{i})]$ contains $K_{2,m}$ as an induced subgraph, a contradiction. Thus $\Delta (H_{i})\leq m-1$. Since $H_{i}$ is $P_{7}$-free, we also have $\mbox{diam}(H_{i})\leq 5$. Consequently $|V(H_{i})|\leq (m-1)^{5}$ for each $1\leq i\leq p$. Since $|A\cup B|\geq 2(2(m-1)^{7}-m+1)$, it follows that $p\geq 2(2(m-1)^{7}-m+1)/(m-1)^{5}>3(m-1)^{2}+2$. Since $k=4$, $|V(H_{i})|\geq 2$ for some $i$. We may assume that $|V(H_{1})|\geq 2$. Let $a_{1}b_{1}\in E(H_{1})$ with $a_{1}\in A$ and $b_{1}\in B$. Note that each vertex in $N(a)\cap N(b)$ is an isolated vertex in $G[N(a)\cup N(b)]$. Since $G-\{a,b\}$ is connected, this implies that for each $2\leq i\leq p$, there exists $x_{i}\in V(H_{i})$ such that $N(x_{i})-(\{a,b\}\cup N(a)\cup N(b))\not=\emptyset $. Let $X=\{x_{i}\mid 2\leq i\leq p\}$. Let $A_{0}=\{x\in A\cap X\mid N(x)-(\{a,b\}\cup N(a)\cup N(b))\subseteq N(w)\}$ and $A_{1}=(A\cap X)-A_{0}$. For each $x\in A\cap X$, we define $u_{x}\in N(x)$ as follows: if $x\in A_{0}$, let $u_{x}\in N(x)-(\{a,b\}\cup N(a)\cup N(b))$; if $x\in A_{1}$, let $u_{x}\in N(x)-(\{a,b\}\cup N(a)\cup N(b))-N(w)$. For $A'\subseteq A\cap X$, let $U_{A'}=\{u_{x}\mid x\in A'\}$. Let $B_{0}=\{y\in B\cap X\mid N(y)-(\{a,b\}\cup N(a)\cup N(b))\subseteq N(w)\}$ and $B_{1}=(B\cap X)-B_{0}$. For each $y\in B\cap X$, we define $v_{y}\in N(y)$ as follows: if $y\in B_{0}$, let $v_{y}\in N(y)-(\{a,b\}\cup N(a)\cup N(b))$; if $y\in B_{1}$, let $v_{y}\in N(y)-(\{a,b\}\cup N(a)\cup N(b))-N(w)$. For $B'\subseteq B\cap X$, let $V_{B'}=\{v_{y}\mid y\in B'\}$. Note that $|A_{0}|+|A_{1}|+|B_{0}|+|B_{1}|=|X|=p-1$. Arguing as in the proof of Claim~\ref{ns3 lem4 cl1}, we obtain the following claim. \begin{claim}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns3 lem4 cl2} For $A'\subseteq A\cap X$, $|U_{A'}|\geq |A'|/(m-1)$. For $B'\subseteq B\cap X$, $|V_{B'}|\geq |B'|/(m-1)$. \end{claim} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Here we consider the following three subcases:\\ (1) $|A_{0}|>(m-1)^{2}$ or $|B_{0}|>(m-1)^{2}$;\\ (2) $|A_{0}|\leq (m-1)^{2}$ and $|B_{0}|\leq (m-1)^{2}$ and, moreover, we have $A_{1}\not=\emptyset $ and $B_{1}\not=\emptyset $;\\ (3) $|A_{0}|\leq (m-1)^{2}$ and $|B_{0}|\leq (m-1)^{2}$, but we have $A_{1}=\emptyset $ or $B_{1}=\emptyset $. \medskip \noindent \textbf{Subcase 2.1:} $|A_{0}|>(m-1)^{2}$ or $|B_{0}|>(m-1)^{2}$ We may assume that $|A_{0}|>(m-1)^{2}$. By Claim~\ref{ns3 lem4 cl2}, $|U_{A_{0}}|\geq m$. Note that $U_{A_{0}}\subseteq N(w)$. Since $G$ is $K_{2,m}$-free, $|N(a_{1})\cap U_{A_{0}}|\leq m-1$. Since $|U_{A_{0}}|\geq m$, there exists $x\in A_{0}$ such that $u_{x}a_{1}\not\in E(G)$. We may assume that $x=x_{2}$. Since $x_{2}$ and $b_{1}$ belong to distinct components of $G[A\cup B]$, $x_{2}b_{1}\not\in E(G)$. Since $|B|\geq 2(m-1)^{7}-m+1>2(m-1)^{5}\geq |V(H_{1})|+|V(H_{2})|$, $B-(V(H_{1})\cup V(H_{2}))\not=\emptyset $. Let $y\in B-(V(H_{1})\cup V(H_{2}))$. Then $ya_{1},yx_{2}\not\in E(G)$. Since $k=4$, we also have $u_{x_{2}}b_{1},u_{x_{2}}y\not\in E(G)$. Since $u_{x_{2}}\not\in N(a)\cup N(b)$, we now see that the path $u_{x_{2}}x_{2}aa_{1}b_{1}by$ is an induced path of order $7$, a contradiction. \medskip \noindent \textbf{Subcase 2.2:} $|A_{0}|\leq (m-1)^{2}$ and $|B_{0}|\leq (m-1)^{2}$ and, moreover, we have $A_{1}\not=\emptyset $ and $B_{1}\not=\emptyset $ Let $x\in A_{1}$ and $y\in B_{1}$. By the definition of $X$, $x$ and $y$ belong to distinct components of $G[A\cup B]$, and hence $xy\not\in E(G)$. Since $u_{x},v_{y}\not\in N(a)\cup N(b)\cup N(w)$ and $k=4$, it follows that the path $u_{x}xawbyv_{y}$ is an induced path of order $7$, a contradiction. \medskip \noindent \textbf{Subcase 2.3:} $|A_{0}|\leq (m-1)^{2}$ and $|B_{0}|\leq (m-1)^{2}$, but we have $A_{1}=\emptyset $ or $B_{1}=\emptyset $ We may assume that $A_{1}=\emptyset $. Then $3(m-1)^{2}+1(m-1)^{2}+1$. On the other hand, since $|A|\geq 2(m-1)^{7}-m+1>(m-1)^{2}(m-1)^{5}\geq |A_{0}|(m-1)^{5}=|A_{0}\cup A_{1}|(m-1)^{5}=|A\cap X|(m-1)^{5}$ and since $|V(H_{i})|\leq (m-1)^{5}$ for each $2\leq i\leq p$, there exists $i$ with $2\leq i\leq p$ such that $V(H_{i})\cap A\not=\emptyset $ and $x_{i}\not\in A$. We may assume that $V(H_{2})\cap A\not=\emptyset $ and $x_{2}\not\in A$. Then $x_{2}\in B$, which implies $|V(H_{2})|\geq 2$. Let $a_{2}b_{2}\in E(H_{2})$ with $a_{2}\in A$ and $b_{2}\in B$. Now since $|B_{1}-\{x_{2}\}|>(m-1)^{2}$, $|V_{B_{1}-\{x_{2}\}}|\geq m$ by Claim~\ref{ns3 lem4 cl2}. Since $G$ is $K_{3}$-free, it follows that if both $b_{1}$ and $b_{2}$ are adjacent to all vertices in $V_{B_{1}-\{x_{2}\}}$, then $G[\{b_{1},b_{2}\}\cup V_{B_{1}-\{x_{2}\}}]$ contains $K_{2,m}$ as an induced subgraph, a contradiction. Thus $b_{h}v_{y}\not\in E(G)$ for some $h\in \{1,2\}$ and some $y\in B_{1}-\{x_{2}\}$. We may assume that $y=x_{3}$. Since $|A|\geq 2(m-1)^{7}-m+1>3(m-1)^{5}\geq |V(H_{1})|+|V(H_{2})|+|V(H_{3})|$, $A-(V(H_{1})\cup V(H_{2})\cup V(H_{3}))\not=\emptyset $. Let $x\in A-(V(H_{1})\cup V(H_{2})\cup V(H_{3}))$. Since $v_{x_{3}}\not\in N(a)\cup N(b)$ and $k=4$, the path $xaa_{h}b_{h}bx_{3}v_{x_{3}}$ is an induced path of order $7$, a contradiction. \medskip \noindent \textbf{Case 3:} $k\geq 5$ If $k=5$, then by Lemma~\ref{ns3 lem2} and the assumption that $d(a)\geq 2(m-1)^{7}\geq 4(m-1)+2$ and $d(b)\geq 2(m-1)^{7}\geq 4(m-1)+2$, $G$ contains $P_{7}$ as an induced subgraph, a contradiction; if $k\geq 6$, then by Lemma~\ref{ns3 lem1} and the assumption that $d(a)\geq 2(m-1)^{7}\geq 4(m-1)+2$, $G$ contains $P_{7}$ as an induced subgraph, a contradiction. This completes the proof of Lemma~\ref{ns3 lem4}. \qed \begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{ns3 prop2} Let $m\geq 5$. Then $\G _{3}(\{K_{3},K_{2,m},P_{7}\})$ is finite. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Let $G\in \G _{3}(\{K_{3},K_{2,m},P_{7}\})$. We show that $|V(G)|\leq (4(m-1)^{7}(2(m-1)^{7}+m-2)^{5})^{5}$. Since $\mbox{diam}(G)\leq 5$, it suffices to show that $\Delta (G)\leq 4(m-1)^{7}(2(m-1)^{7}+m-2)^{5}$. Suppose that $\Delta (G)\geq 4(m-1)^{7}(2(m-1)^{7}+m-2)^{5}+1$, and let $w\in V(G)$ be a vertex with $d(w)=\Delta (G)$. Since $G$ is $K_{3}$-free, $N(w)$ is independent. Let $L=\{x\in V(G)\mid |N(x)\cap N_{2}(w)|\geq 2(m-1)^{7}\}$. By Lemma~\ref{ns3 lem4}, $|L\cap N(w)|\leq 1$ and $L\cap N_{2}(w)=\emptyset $. \medskip \noindent \textbf{Case 1:} $|L|\geq 2$ and $|L\cap N(w)|=1$ Let $a\in L\cap N(w)$ and $b\in L-N(w)$. Since $b\not\in N(w)\cup N_{2}(w)$, we have $b\in N_{3}(w)$, and hence $ab\not\in E(G)$. By Lemma~\ref{ns3 lem4}, $N(a)\cap N(b)=\emptyset $. Let $y\in N(b)\cap N_{2}(w)$ and $v\in N(y)\cap N(w)$. Since $ab\not\in E(G)$, $N(a)\cap N(b)=\emptyset $, and $N(w)$ is independent, it follows that the path $awvyb$ is an induced path of order $5$. Hence by Lemma~\ref{ns3 lem2} and the assumption that $d(a)\geq 2(m-1)^{7}\geq 4(m-1)+2$ and $d(b)\geq 2(m-1)^{7}\geq 4(m-1)+2$, $G$ contains $P_{7}$ as an induced subgraph, a contradiction. \medskip \noindent \textbf{Case 2:} $|L|\geq 2$ and $L\cap N(w)=\emptyset $ Let $a,b\in L$ with $a\not=b$. Then $a,b\in N_{3}(w)$. If $ab\in E(G)$, then $N(a)\cap N(b)=\emptyset $ by the assumption that $G$ is $K_{3}$-free and, if $ab\not\in E(G)$, then $N(a)\cap N(b)=\emptyset $ by Lemma~\ref{ns3 lem4}. Hence in either case, we have $N(a)\cap N(b)=\emptyset $. Let $A=N(a)\cap N_{2}(w)$ and $B=N(b)\cap N_{2}(w)$. Let $y\in B$ and $v\in N(y)\cap N(w)$. Since $G$ is $K_{2,m}$-free, $|N(y)\cap N(w)|\leq m-1$. Since $G$ is $K_{2,m}$-free, it follows that $|((\bigcup_{u\in N(y)\cap N(w)}N(u))\cup N(y))\cap A|\leq (|N(y)\cap N(w)|+1)(m-1)\leq m(m-1)$. Since $|A|\geq 2(m-1)^{7}\geq m(m-1)+1$, $A-((\bigcup_{u\in N(y)\cap N(w)}N(u))\cup N(y))\not=\emptyset $. Take $x\in A-((\bigcup_{u\in N(y)\cap N(w)}N(u))\cup N(y))$. Since $v\in N(y)\cap N(w)$, we have $xv,xy\not\in E(G)$. Take $u\in N(x)\cap N(w)$. By the choice of $x$, $u\not\in N(y)\cap N(w)$, and hence $uy\not\in E(G)$. Consequently the path $xuwvyb$ is an induced path of order $6$. Now by Lemma~\ref{ns3 lem1} and the assumption that $d(b)\geq 2(m-1)^{7}\geq 4(m-1)+2$, $G$ contains $P_{7}$ as an induced subgraph, a contradiction. \medskip \noindent \textbf{Case 3:} $|L|\leq 1$ Let $H_{1},\ldots ,H_{p}$ be the components of $G[(N(w)\cup N_{2}(w))-L]$. Let $1\leq i\leq p$. Take $x\in V(H_{i})$. Since $G$ is $\{K_{3},K_{2,m}\}$-free, $|N(x)\cap N(w)|\leq m-1$. Since $x\not\in L$, we also have $|N(x)\cap N_{2}(w)|\leq 2(m-1)^{7}-1$. Hence $d_{H_{i}}(x)\leq |N(x)\cap N(w)|+|N(x)\cap N_{2}(w)|\leq 2(m-1)^{7}+m-2$. Since $x\in V(H_{i})$ is arbitrary, $\Delta (H_{i})\leq 2(m-1)^{7}+m-2$. Since $H_{i}$ is $P_{7}$-free, we also have $\mbox{diam}(H_{i})\leq 5$. Thus $|V(H_{i})|\leq (2(m-1)^{7}+m-2)^{5}$ for each $1\leq i\leq p$. We have $V(H_{i})\cap N_{2}(w)\not=\emptyset $ for each $1\leq i\leq p$ because $N(w)$ is independent. Let $q=|\{i\mid V(H_{i})\cap N(w)\not=\emptyset \}|$. (Note that in the case where $\emptyset \not=L\subseteq N(w)$, it is possible that $V(H_{i})\cap N(w)=\emptyset $ for some $i$.) Without loss of generality, we may assume that $V(H_{i})\cap N(w)\not=\emptyset $ for each $1\leq i\leq q$ and $V(H_{i})\cap N(w)=\emptyset $ for each $q+1\leq i\leq p$. Since $|N(w)-L|\geq d(w)-1\geq 4(m-1)^{7}(2(m-1)^{7}+m-2)^{5}$, we have $q\geq |N(w)-L|/(2(m-1)^{7}+m-2)^{5}\geq 4(m-1)^{7}$. Since $G$ is $3$-connected, $G-(\{w\}\cup L)$ is connected. Let $P$ be a shortest $V(H_{1})$-$((N(w)\cup N_{2}(w))-L-V(H_{1}))$ path in $G-(\{w\}\cup L)$. Then $|V(P)|\geq 3$. Let $y_{1}$, $z_{1}$ and $z_{2}$ be the first three vertices of $P$. Then $y_{1}\in V(H_{1})\cap N_{2}(w)$ and $z_{1}\in N_{3}(w)$. Let $wx_{1}y_{1}$ be a shortest $w$-$y_{1}$ path in $G[V(H_{1})\cup \{w\}]$. Then $wx_{1}y_{1}z_{1}z_{2}$ is an induced $w$-$z_{2}$ path of order $5$. Since $z_{1}\not\in L$, $|N(z_{1})\cap N_{2}(w)|\leq 2(m-1)^{7}-1$. In particular, $z_{1}$ is adjacent to at most $2(m-1)^{7}-1$ of the $H_{i}$, $1\leq i\leq q$. If $z_{2}\not\in N_{2}(w)$, then similarly, $z_{2}$ is adjacent to at most $2(m-1)^{7}-1$ of the $H_{i}$, $1\leq i\leq q$; if $z_{2}\in N_{2}(w)$, then clearly $z_{2}$ is adjacent to at most one of the $H_{i}$, $1\leq i\leq q$ (note that it is possible that $z_{2}$ belongs to $H_{i}$ for some $i$ with $q+1\leq i\leq p$). Thus $z_{2}$ is adjacent to at most $2(m-1)^{7}-1$ of the $H_{i}$. Since $q\geq 4(m-1)^{7}$, there exists $j$ with $2\leq j\leq q$ such that neither $z_{1}$ nor $z_{2}$ is adjacent to $H_{j}$. Since $V(H_{j})\cap N(w)\not=\emptyset $ and $V(H_{j})\cap N_{2}(w)\not=\emptyset $, there exist $x_{2}\in V(H_{j})\cap N(w)$ and $y_{2}\in V(H_{j})\cap N_{2}(w)$ such that $x_{2}y_{2}\in E(G)$. Then $y_{2}x_{2}wx_{1}y_{1}z_{1}z_{2}$ is an induced path of order $7$, a contradiction. This completes the proof of Proposition~\ref{ns3 prop2}. \qed \medbreak\noindent\textit{Proof of Theorem~\ref{ns3}.}\quad The `if ' part follows from Propositions~\ref{ns3 prop1} and \ref{ns3 prop2}. Thus it suffices to prove the `only if' part. Suppose that $\G _{3}(\{K_{3},K_{2,m},T\})$ is finite. From Theorem~\ref{nec}, it follows that $T\in \T _{2}$. For each $s\geq 2$, let $H^{(1)}_{s}$ be the graph defined by $V(H^{(1)}_{s})=\{x_{1},x_{2},x_{3}\}\cup \{y_{i,h},z_{i,h}\mid 1\leq i\leq 2,1\leq h\leq s\}$ and $E(H^{(1)}_{s})=\{x_{1}x_{2}\}\cup \{x_{i}y_{i,h},x_{3}z_{i,h}\mid 1\leq i\leq 2,1\leq h\leq s\}\cup \{y_{i,h}z_{j,h}\mid 1\leq i,j\leq 2,1\leq h\leq s\}$. Then $H^{(1)}_{s}$ is $3$-connected and $\{K_{3},K_{2,m}\}$-free. Since $\G _{3}(\{K_{3},K_{2,m},T\})$ is finite, there exists $s\geq 2$ such that $H^{(1)}_{s}$ contains $T$ as an induced subgraph. Since every tree contained in $H^{(1)}_{s}$ as an induced subgraph has diameter at most $6$, $\mbox{diam}(T)\leq 6$. Now for each $t\geq 3$, let $P=x_{1}x_{2}$ be a path of order $2$ and $C=y_{1}y_{2}\cdots y_{2t}y_{1}$ be a cycle of order $2t$, and let $H^{(2)}_{t}$ be the graph defined by $V(H^{(2)}_{t})=V(C)\cup V(P)$ and $E(H^{(2)}_{t})=E(C)\cup E(P)\cup \{x_{1}y_{2i-1},x_{2}y_{2i}\mid 1\leq i\leq t\}$. Then $H^{(2)}_{t}$ is $3$-connected and $\{K_{3},K_{2,m}\}$-free. Hence there exists $t\geq 3$ such that $H^{(2)}_{t}$ contains $T$ as an induced subgraph. Observe that if $F$ is a member of $\T _{2}$ contained in $H^{(2)}_{t}$ as an induced subgraph, then $F$ is a path or an induced subgraph of $Y^{*}_{3}$. Therefore $T$ is either a path of order at most $7$ or an induced subgraph of $Y^{*}_{3}$. \qed \begin{figure} \begin{center} %WinTpicVersion4.10 \unitlength 0.1in \begin{picture}( 60.6500, 21.5000)( 5.3000,-29.3500) % CIRCLE 2 0 0 0 Black Black % 4 2200 2800 2250 2800 2250 2800 2250 2800 % \special{sh 1.000}% \special{ia 2200 2800 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2200 2800 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1000 2200 1050 2200 1050 2200 1050 2200 % \special{sh 1.000}% \special{ia 1000 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1000 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1200 2200 1250 2200 1250 2200 1250 2200 % \special{sh 1.000}% \special{ia 1200 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1200 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1200 1600 1250 1600 1250 1600 1250 1600 % \special{sh 1.000}% \special{ia 1200 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1200 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1000 1600 1050 1600 1050 1600 1050 1600 % \special{sh 1.000}% \special{ia 1000 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1000 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2200 2800 2250 2800 2250 2800 2250 2800 % \special{sh 1.000}% \special{ia 2200 2800 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2200 2800 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1800 1000 1850 1000 1850 1000 1850 1000 % \special{sh 1.000}% \special{ia 1800 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1800 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2400 1000 2450 1000 2450 1000 2450 1000 % \special{sh 1.000}% \special{ia 2400 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2400 1000 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1800 2200 1850 2200 1850 2200 1850 2200 % \special{sh 1.000}% \special{ia 1800 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1800 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2000 2200 2050 2200 2050 2200 2050 2200 % \special{sh 1.000}% \special{ia 2000 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2000 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 2000 1600 2050 1600 2050 1600 2050 1600 % \special{sh 1.000}% \special{ia 2000 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 2000 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 1800 1600 1850 1600 1850 1600 1850 1600 % \special{sh 1.000}% \special{ia 1800 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 1800 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3200 2200 3250 2200 3250 2200 3250 2200 % \special{sh 1.000}% \special{ia 3200 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3200 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3400 2200 3450 2200 3450 2200 3450 2200 % \special{sh 1.000}% \special{ia 3400 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3400 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3400 1600 3450 1600 3450 1600 3450 1600 % \special{sh 1.000}% \special{ia 3400 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3400 1600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 3200 1600 3250 1600 3250 1600 3250 1600 % \special{sh 1.000}% \special{ia 3200 1600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 3200 1600 50 50 0.0000000 6.2831853}% % DOT 0 0 3 0 Black Black % 4 2500 1900 2700 1900 2600 1900 2600 1900 % \special{pn 4}% \special{sh 1}% \special{ar 2500 1900 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 2700 1900 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 2600 1900 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 2600 1900 14 14 0 6.28318530717959E+0000}% % CIRCLE 2 0 3 0 Black Black % 4 5595 1800 4795 1800 4795 1800 4795 1800 % \special{pn 8}% \special{ar 5596 1800 800 800 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4795 1800 4845 1800 4845 1800 4845 1800 % \special{sh 1.000}% \special{ia 4796 1800 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4796 1800 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4905 2200 4955 2200 4955 2200 4955 2200 % \special{sh 1.000}% \special{ia 4906 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4906 2200 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4905 1400 4955 1400 4955 1400 4955 1400 % \special{sh 1.000}% \special{ia 4906 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4906 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 5155 1130 5205 1130 5205 1130 5205 1130 % \special{sh 1.000}% \special{ia 5156 1130 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 5156 1130 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 5155 2470 5205 2470 5205 2470 5205 2470 % \special{sh 1.000}% \special{ia 5156 2470 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 5156 2470 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 5595 2600 5645 2600 5645 2600 5645 2600 % \special{sh 1.000}% \special{ia 5596 2600 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 5596 2600 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4905 1400 4955 1400 4955 1400 4955 1400 % \special{sh 1.000}% \special{ia 4906 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4906 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 5595 1000 5645 1000 5645 1000 5645 1000 % \special{sh 1.000}% \special{ia 5596 1000 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 5596 1000 50 50 0.0000000 6.2831853}% % BOX 2 5 2 0 Black White % 2 5995 1000 6595 2600 % \special{pn 0}% \special{sh 0}% \special{pa 5996 1000}% \special{pa 6596 1000}% \special{pa 6596 2600}% \special{pa 5996 2600}% \special{pa 5996 1000}% \special{ip}% \special{pn 8}% \special{pa 5996 1000}% \special{pa 6596 1000}% \special{pa 6596 2600}% \special{pa 5996 2600}% \special{pa 5996 1000}% \special{ip}% % DOT 0 5 3 0 Black Black % 4 6395 1800 6295 1500 6295 2100 6295 2100 % \special{pn 4}% \special{sh 1}% \special{ar 6396 1800 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 6296 1500 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 6296 2100 14 14 0 6.28318530717959E+0000}% \special{sh 1}% \special{ar 6296 2100 14 14 0 6.28318530717959E+0000}% % CIRCLE 2 0 0 0 Black Black % 4 4395 1400 4445 1400 4445 1400 4445 1400 % \special{sh 1.000}% \special{ia 4396 1400 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4396 1400 50 50 0.0000000 6.2831853}% % CIRCLE 2 0 0 0 Black Black % 4 4395 2200 4445 2200 4445 2200 4445 2200 % \special{sh 1.000}% \special{ia 4396 2200 50 50 0.0000000 6.2831853}% \special{pn 8}% \special{ar 4396 2200 50 50 0.0000000 6.2831853}% % LINE 2 0 3 0 Black Black % 10 4395 1400 4395 2200 4395 1400 5155 1130 4795 1800 4395 1400 4395 2200 4905 2200 4905 1400 4395 2200 % \special{pn 8}% \special{pa 4396 1400}% \special{pa 4396 2200}% \special{fp}% \special{pa 4396 1400}% \special{pa 5156 1130}% \special{fp}% \special{pa 4796 1800}% \special{pa 4396 1400}% \special{fp}% \special{pa 4396 2200}% \special{pa 4906 2200}% \special{fp}% \special{pa 4906 1400}% \special{pa 4396 2200}% \special{fp}% % SPLINE 2 0 3 0 Black Black % 5 4395 2200 4795 1200 5195 1000 5595 1000 5595 1000 % \special{pn 8}% \special{pa 4396 2200}% \special{pa 4414 2098}% \special{pa 4420 2064}% \special{pa 4426 2032}% \special{pa 4432 1998}% \special{pa 4440 1964}% \special{pa 4454 1898}% \special{pa 4470 1832}% \special{pa 4486 1768}% \special{pa 4504 1704}% \special{pa 4524 1642}% \special{pa 4534 1610}% \special{pa 4546 1580}% \special{pa 4558 1552}% \special{pa 4570 1522}% \special{pa 4584 1494}% \special{pa 4598 1464}% \special{pa 4612 1438}% \special{pa 4628 1410}% \special{pa 4644 1384}% \special{pa 4660 1358}% \special{pa 4678 1332}% \special{pa 4696 1306}% \special{pa 4716 1282}% \special{pa 4736 1260}% \special{pa 4758 1236}% \special{pa 4780 1214}% \special{pa 4804 1194}% \special{pa 4828 1172}% \special{pa 4854 1154}% \special{pa 4880 1134}% \special{pa 4906 1116}% \special{pa 4934 1100}% \special{pa 4962 1084}% \special{pa 4992 1068}% \special{pa 5022 1054}% \special{pa 5052 1042}% \special{pa 5082 1030}% \special{pa 5114 1020}% \special{pa 5176 1004}% \special{pa 5208 998}% \special{pa 5238 994}% \special{pa 5302 988}% \special{pa 5334 986}% \special{pa 5398 986}% \special{pa 5430 988}% \special{pa 5494 992}% \special{pa 5558 998}% \special{pa 5592 1000}% \special{pa 5596 1000}% \special{sp}% % SPLINE 2 0 3 0 Black Black % 4 5595 2600 4795 2600 4395 2200 4395 2200 % \special{pn 8}% \special{pa 5596 2600}% \special{pa 5560 2608}% \special{pa 5526 2614}% \special{pa 5492 2620}% \special{pa 5456 2626}% \special{pa 5422 2632}% \special{pa 5388 2638}% \special{pa 5354 2644}% \special{pa 5320 2648}% \special{pa 5286 2652}% \special{pa 5252 2656}% \special{pa 5220 2660}% \special{pa 5154 2664}% \special{pa 5122 2664}% \special{pa 5090 2664}% \special{pa 5058 2664}% \special{pa 5026 2662}% \special{pa 4996 2658}% \special{pa 4966 2654}% \special{pa 4936 2648}% \special{pa 4906 2642}% \special{pa 4878 2634}% \special{pa 4850 2624}% \special{pa 4822 2612}% \special{pa 4796 2600}% \special{pa 4770 2586}% \special{pa 4744 2570}% \special{pa 4718 2554}% \special{pa 4694 2536}% \special{pa 4670 2516}% \special{pa 4646 2496}% \special{pa 4624 2474}% \special{pa 4602 2452}% \special{pa 4558 2404}% \special{pa 4536 2378}% \special{pa 4514 2352}% \special{pa 4492 2326}% \special{pa 4472 2300}% \special{pa 4452 2274}% \special{pa 4410 2220}% \special{pa 4396 2200}% \special{sp}% % SPLINE 2 0 3 0 Black Black % 5 5155 2470 4555 2070 4405 1400 4405 1400 4405 1400 % \special{pn 8}% \special{pa 5156 2470}% \special{pa 5124 2456}% \special{pa 5092 2442}% \special{pa 5060 2428}% \special{pa 5030 2412}% \special{pa 4998 2398}% \special{pa 4968 2384}% \special{pa 4938 2368}% \special{pa 4878 2336}% \special{pa 4848 2320}% \special{pa 4820 2304}% \special{pa 4792 2288}% \special{pa 4766 2270}% \special{pa 4740 2252}% \special{pa 4714 2234}% \special{pa 4690 2214}% \special{pa 4666 2194}% \special{pa 4644 2174}% \special{pa 4622 2152}% \special{pa 4602 2130}% \special{pa 4582 2108}% \special{pa 4564 2084}% \special{pa 4548 2058}% \special{pa 4532 2034}% \special{pa 4518 2008}% \special{pa 4506 1980}% \special{pa 4494 1952}% \special{pa 4484 1924}% \special{pa 4474 1894}% \special{pa 4464 1864}% \special{pa 4456 1834}% \special{pa 4450 1802}% \special{pa 4438 1738}% \special{pa 4432 1706}% \special{pa 4424 1640}% \special{pa 4420 1606}% \special{pa 4414 1538}% \special{pa 4412 1504}% \special{pa 4410 1470}% \special{pa 4408 1434}% \special{pa 4406 1400}% \special{sp}% % LINE 2 0 3 0 Black Black % 8 1000 2200 1000 1600 1000 1600 1200 2200 1200 2200 1200 1600 1200 1600 1000 2200 % \special{pn 8}% \special{pa 1000 2200}% \special{pa 1000 1600}% \special{fp}% \special{pa 1000 1600}% \special{pa 1200 2200}% \special{fp}% \special{pa 1200 2200}% \special{pa 1200 1600}% \special{fp}% \special{pa 1200 1600}% \special{pa 1000 2200}% \special{fp}% % LINE 2 0 3 0 Black Black % 8 1800 2200 1800 1600 1800 1600 2000 2200 2000 2200 2000 1600 2000 1600 1800 2200 % \special{pn 8}% \special{pa 1800 2200}% \special{pa 1800 1600}% \special{fp}% \special{pa 1800 1600}% \special{pa 2000 2200}% \special{fp}% \special{pa 2000 2200}% \special{pa 2000 1600}% \special{fp}% \special{pa 2000 1600}% \special{pa 1800 2200}% \special{fp}% % LINE 2 0 3 0 Black Black % 8 3200 2200 3200 1600 3200 1600 3400 2200 3400 2200 3400 1600 3400 1600 3200 2200 % \special{pn 8}% \special{pa 3200 2200}% \special{pa 3200 1600}% \special{fp}% \special{pa 3200 1600}% \special{pa 3400 2200}% \special{fp}% \special{pa 3400 2200}% \special{pa 3400 1600}% \special{fp}% \special{pa 3400 1600}% \special{pa 3200 2200}% \special{fp}% % LINE 2 0 3 0 Black Black % 16 3400 2200 2200 2800 2200 2800 3200 2200 3200 2200 3200 2200 2000 2200 2000 2200 2000 2200 2200 2800 2200 2800 1800 2200 1200 2200 2200 2800 2200 2800 1000 2200 % \special{pn 8}% \special{pa 3400 2200}% \special{pa 2200 2800}% \special{fp}% \special{pa 2200 2800}% \special{pa 3200 2200}% \special{fp}% \special{pa 3200 2200}% \special{pa 3200 2200}% \special{fp}% \special{pa 2000 2200}% \special{pa 2000 2200}% \special{fp}% \special{pa 2000 2200}% \special{pa 2200 2800}% \special{fp}% \special{pa 2200 2800}% \special{pa 1800 2200}% \special{fp}% \special{pa 1200 2200}% \special{pa 2200 2800}% \special{fp}% \special{pa 2200 2800}% \special{pa 1000 2200}% \special{fp}% % LINE 2 0 3 0 Black Black % 14 1000 1600 1800 1000 1800 1000 1800 1600 3200 1600 1800 1000 1800 1000 2400 1000 2400 1000 1200 1600 2000 1600 2400 1000 2400 1000 3400 1600 % \special{pn 8}% \special{pa 1000 1600}% \special{pa 1800 1000}% \special{fp}% \special{pa 1800 1000}% \special{pa 1800 1600}% \special{fp}% \special{pa 3200 1600}% \special{pa 1800 1000}% \special{fp}% \special{pa 1800 1000}% \special{pa 2400 1000}% \special{fp}% \special{pa 2400 1000}% \special{pa 1200 1600}% \special{fp}% \special{pa 2000 1600}% \special{pa 2400 1000}% \special{fp}% \special{pa 2400 1000}% \special{pa 3400 1600}% \special{fp}% % STR 2 0 3 0 Black White % 4 1800 750 1800 850 5 0 0 0 % $x_{1}$ \put(18.0000,-8.5000){\makebox(0,0){$x_{1}$}}% % STR 2 0 3 0 Black White % 4 2400 750 2400 850 5 0 0 0 % $x_{2}$ \put(24.0000,-8.5000){\makebox(0,0){$x_{2}$}}% % STR 2 0 3 0 Black White % 4 800 1500 800 1600 5 0 0 0 % $y_{1,1}$ \put(8.0000,-16.0000){\makebox(0,0){$y_{1,1}$}}% % STR 2 0 3 0 Black White % 4 800 2100 800 2200 5 0 0 0 % $z_{1,1}$ \put(8.0000,-22.0000){\makebox(0,0){$z_{1,1}$}}% % STR 2 0 3 0 Black White % 4 1400 1550 1400 1650 5 0 0 0 % $y_{2,1}$ \put(14.0000,-16.5000){\makebox(0,0){$y_{2,1}$}}% % STR 2 0 3 0 Black White % 4 1400 2050 1400 2150 5 0 0 0 % $z_{2,1}$ \put(14.0000,-21.5000){\makebox(0,0){$z_{2,1}$}}% % STR 2 0 3 0 Black White % 4 1600 1450 1600 1550 5 0 0 0 % $y_{1,2}$ \put(16.0000,-15.5000){\makebox(0,0){$y_{1,2}$}}% % STR 2 0 3 0 Black White % 4 1600 2150 1600 2250 5 0 0 0 % $z_{1,2}$ \put(16.0000,-22.5000){\makebox(0,0){$z_{1,2}$}}% % STR 2 0 3 0 Black White % 4 2200 1500 2200 1600 5 0 0 0 % $y_{2,2}$ \put(22.0000,-16.0000){\makebox(0,0){$y_{2,2}$}}% % STR 2 0 3 0 Black White % 4 2200 2100 2200 2200 5 0 0 0 % $z_{2,2}$ \put(22.0000,-22.0000){\makebox(0,0){$z_{2,2}$}}% % STR 2 0 3 0 Black White % 4 3600 1500 3600 1600 5 0 0 0 % $y_{2,s}$ \put(36.0000,-16.0000){\makebox(0,0){$y_{2,s}$}}% % STR 2 0 3 0 Black White % 4 3600 2100 3600 2200 5 0 0 0 % $z_{2,s}$ \put(36.0000,-22.0000){\makebox(0,0){$z_{2,s}$}}% % STR 2 0 3 0 Black White % 4 3000 1500 3000 1600 5 0 0 0 % $y_{1,s}$ \put(30.0000,-16.0000){\makebox(0,0){$y_{1,s}$}}% % STR 2 0 3 0 Black White % 4 3000 2100 3000 2200 5 0 0 0 % $z_{1,s}$ \put(30.0000,-22.0000){\makebox(0,0){$z_{1,s}$}}% % STR 2 0 3 0 Black White % 4 2200 2900 2200 3000 5 0 0 0 % $x_{3}$ \put(22.0000,-30.0000){\makebox(0,0){$x_{3}$}}% % STR 2 0 3 0 Black White % 4 4195 1300 4195 1400 5 0 0 0 % $x_{1}$ \put(41.9500,-14.0000){\makebox(0,0){$x_{1}$}}% % STR 2 0 3 0 Black White % 4 4195 2100 4195 2200 5 0 0 0 % $x_{2}$ \put(41.9500,-22.0000){\makebox(0,0){$x_{2}$}}% % STR 2 0 3 0 Black White % 4 5595 1100 5595 1200 2 0 0 0 % \put(55.9500,-12.0000){\makebox(0,0)[lb]{}}% % STR 2 0 3 0 Black White % 4 5595 1070 5595 1170 5 0 0 0 % $y_{2t}$ \put(55.9500,-11.7000){\makebox(0,0){$y_{2t}$}}% % STR 2 0 3 0 Black White % 4 5165 1190 5165 1290 5 0 0 0 % $y_{1}$ \put(51.6500,-12.9000){\makebox(0,0){$y_{1}$}}% % STR 2 0 3 0 Black White % 4 5025 1410 5025 1510 5 0 0 0 % $y_{2}$ \put(50.2500,-15.1000){\makebox(0,0){$y_{2}$}}% % STR 2 0 3 0 Black White % 4 4995 1700 4995 1800 5 0 0 0 % $y_{3}$ \put(49.9500,-18.0000){\makebox(0,0){$y_{3}$}}% % STR 2 0 3 0 Black White % 4 5005 1980 5005 2080 5 0 0 0 % $y_{4}$ \put(50.0500,-20.8000){\makebox(0,0){$y_{4}$}}% % STR 2 0 3 0 Black White % 4 5215 2240 5215 2340 5 0 0 0 % $y_{5}$ \put(52.1500,-23.4000){\makebox(0,0){$y_{5}$}}% % STR 2 0 3 0 Black White % 4 5595 2340 5595 2440 5 0 0 0 % $y_{6}$ \put(55.9500,-24.4000){\makebox(0,0){$y_{6}$}}% % STR 2 0 3 0 Black White % 4 890 760 890 860 5 0 0 0 % $H^{(1)}_{s}$ \put(8.9000,-8.6000){\makebox(0,0){$H^{(1)}_{s}$}}% % STR 2 0 3 0 Black White % 4 4145 760 4145 860 5 0 0 0 % $H^{(2)}_{t}$ \put(41.4500,-8.6000){\makebox(0,0){$H^{(2)}_{t}$}}% \end{picture}% \caption{Graphs $H^{(1)}_{s}$ and $H^{(2)}_{t}$} \label{f4} \end{center} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding remarks}\label{sec7} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this paper, we have considered three forbidden subgraphs which generate a finite set in the class of $3$-connected graphs. As we have seen in Theorem~\ref{nec}, there are six types. For many of them, we have given a characterization. The cases which remain uncharacterized are the following:\\ (a) $\F=\{K_{3},K_{3,3},T\}$, where $T\in \T _{2}$;\\ (b) $\F=\{K_{4},K_{2,2},T\}$, where $T$ is a path of order at least $4$;\\ (c) $\F=\{K_{3},K_{2,4},T\}$ and $\{K_{3},K_{2,3},T\}$, where $T\in \T _{1}$;\\ (d) $\F=\{K_{3},K_{2,2},T\}$, where $T\in \T _{0}$;\\ (e) $\F=\{K_{3},K_{1,4},T\}$, where $T\in \T _{1}$;\\ (f) $\F=\{K_{n},K_{1,3},T\}$, where $n\geq 5$ and $T\in \T ^{*}_{2}$;\\ (g) $\F=\{K_{4},K_{1,3},T\}$, where $T\in \T ^{*}_{1}$.\\ In cases (a)--(d), $\F$ does not contain a star. In these cases, we can give a bound on the diameter of $T$. \begin{prop}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{diam finite prop} Let $\F$ be a subset of $\G$ with $|\F|=3$. Suppose $\F$ does not contain a star and $\G _{3}(\F)$ is finite. Then $\F$ contains a tree of diameter at most $8$. \end{prop} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \proof Since $\F$ does not contain a star, it follows from Theorem~\ref{nec} that $\F$ can be written in the form $\F =\{K_{n},K_{m_{1},m_{2}},T\}$, where $n\in \{3,4\}$, $m_{1}\in \{2,3\}$, $m_{2}\geq m_{1}$ and $T\in \T _{0}$. Let $s\geq 2$. Let $C^{(i)}=a^{(i)}_{1}b^{(i)}_{1}c^{(i)}_{1}a^{(i)}_{2}b^{(i)}_{2}c^{(i)}_{2}a^{(i)}_{1}$ be a cycle of order $6$ for each $1\leq i\leq s$, and define a graph $H_{s}$ by $V(H_{s})=\{a_{0},b_{0},c_{0}\}\cup (\bigcup _{1\leq i\leq s}V(C^{(i)}))$ and $E(H_{s})=\{a_{0}a^{(i)}_{j},b_{0}b^{(i)}_{j},c_{0}c^{(i)}_{j}\mid 1\leq i\leq s,1\leq j\leq 2\}\cup (\bigcup _{1\leq i\leq s}E(C^{(i)}))$. Then $H_{s}$ is $3$-connected and $\{K_{n},K_{m_{1},m_{2}}\}$-free. Hence there exists $s\geq 2$ such that $H_{s}$ contains $T$ as an induced subgraph. However, $H_{s}$ does not contain $P_{10}$ as an induced subgraph. Therefore the diameter of $T$ is at most $8$. \qed In (a)--(d), we have $T\in \T _{0}$ and hence $\Delta (T)\leq 3$. By combining this fact and Proposition~\ref{diam finite prop}, we see that the order of $T$ is bounded. Thus the number of triples in these cases is finite. On the other hand, in cases (e)--(g), where the triple contains a star, Proposition~\ref{diam finite prop} gives no further information about $\F$. In fact, Theorem~\ref{Diestel th} shows that in these cases, there exist infinitely many $\F$ such that $\G _{3}(\F)$ is finite. We add that for (a) and (b), and for the case where $\F=\{K_{3},K_{2,4},T\}$ in (c), the determination of $T$ has recently been completed in \cite{EF}. \section*{Acknowledgment} The authors are grateful to the referees for helpful comments. In particular, one of them has pointed out errors in the first version of the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem {D} R.~Diestel. \newblock {\em Graph Theory'' (4th edition)}. \newblock Graduate Texts in Mathematics \textbf{173}, Springer, 2010. \bibitem{EF} Y.~Egawa and M.~Furuya. \newblock Forbidden triples containing a complete graph and a complete bipartite graph of small order. \newblock {\em Graphs Combin.} \textbf{30} (2014) 1149--1162. \bibitem{FPS} J.~Fujisawa, M.D.~Plummer and A.~Saito. \newblock Forbidden subgraphs generating a finite set. \newblock {\em Discrete Math.} \textbf{313} (2013) 1835--1842. \bibitem{K} M.~Kochol. \newblock Snarks without small cycles. \newblock {\em J. Combin. Theory Ser. B} \textbf{67} (1996) 34--47. \end{thebibliography} \end{document}