% EJC papers must begin as follows \documentclass[12pt]{article} \usepackage{e-jc} \newcommand{\qed}{{$\qquad\square$\bigbreak}} % only use standard LaTeX packages % only include essential packages % we recommend these ams packages %\usepackage{amsthm,amsmath,amssymb} \usepackage{amsmath,amsthm,amssymb,latexsym} \newcommand{\qe}{\begin{flushright}~\hbox{\rule[0pt]{0.6em}{1em}}\end{flushright}} \newtheorem{mainthm}{Main Theorem} % 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 % use \sloppy to avoid overly wide text \sloppy % declare theorem-like environments \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{corollary}[thm]{Corollary} \newtheorem{proposition}[thm]{Proposition} \newtheorem{fact}[thm]{Fact} \newtheorem{observation}[thm]{Observation} \newtheorem{clm}[thm]{Claim} \theoremstyle{definition} \newtheorem{definition}[thm]{Definition} \newtheorem{example}[thm]{Example} \newtheorem{conjecture}[thm]{Conjecture} \newtheorem{open}[thm]{Open Problem} \newtheorem{problem}[thm]{Problem} \newtheorem{question}[thm]{Question} \theoremstyle{remark} \newtheorem{remark}[thm]{Remark} \newtheorem{note}[thm]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Generalized Ramsey Numbers for Graphs with Three Disjoint Cycles versus a Complete Graph} % 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{Shinya Fujita\thanks{Supported by the Japan Society for the Promotion of Science Grant-in-Aid for Young Scientists (B) (20740068) .}\\ \small Department of Integrated Design Engeneering\\[-0.8ex] \small Maebashi Institute of Technology\\[-0.8ex] \small 460-1 Kamisadori, Maebashi 371-0816, Japan.\\ \small\tt shinya.fujita.ph.d@gmail.com } % \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{XX}{XX}\\ \small Mathematics Subject Classifications: 05C35} \begin{document} %\includegraphics[width=\textwidth]{pageHeader} \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} Let $\mathcal{F},\mathcal{G}$ be families of graphs. The generalized Ramsey number $r(\mathcal{F}, \mathcal{G})$ denotes the smallest value of $n$ for which every red-blue coloring of $K_n$ yields a red $F \in \mathcal{F}$ or a blue $G\in \mathcal{G}$. Let $\mathcal{F}(k)$ be a family of graphs with $k$ vertex-disjoint cycles. In this paper, we deal with the case where $\mathcal{F}=\mathcal{F}(3), \mathcal{G}=\{K_t\}$ for some fixed $t$ with $t\ge 2$, and prove that $r(\mathcal{F}(3),\mathcal{G})=2t+5$. % keywords are optional \bigskip\noindent \textbf{Keywords:} independence number; Ramsey number; vertex-disjoint cycles \end{abstract} \section{Introduction} %\begin{proof} % Suppose on the contrary that some planar graph is not fabulous.... %\end{proof} All graphs considered in this paper are finite, undirected, and with no loops. For a graph $G$, $V(G)$, $E(G)$, and $\delta (G)$ denote the set of vertices and the set of edges and the minimum degree of $G$, respectively. For a given graph $G$ and a vertex $x \in V(G)$, we write $N_G (x)$ for the neighborhood of $V(G)$ and let $d_G (x) = |N_{G}(x)|$. Also, for a subgraph $H$ of $G$ and a vertex $x\in V(H)$, let $d_H (x) = |N_{G}(x)\cap V(H)|$. Let $E(A,B)$ be the set of edges between $A$ and $B$ where $A$ and $B$ are vertex subsets with $A \cap B=\emptyset$. When $A$ consists of one vertex, say, $A=\{v\}$, we often write $E(v,B)$ in place of $E(\{v\},B)$. For a subset $S$ of $V(G)$, the subgraph induced by $S$ in $G$ is denoted by $\langle S\rangle$. Let $k$ be an integer with $k\ge 1$. We define the following family of graphs. \begin{center}$\mathcal{F}(k)=\{ H |\ $ $H$ is a graph which contains $k$ vertex-disjoint cycles $\ \}$. \end{center} Also let $\mathcal{F}(0)$ be a family consisting of all simple graphs. By definition, note that $\mathcal{F}(k)\subset \mathcal{F}(k-1)$ holds for every $k\ge 1$. Graphs in $\mathcal{F}(k)$ have attracted a lot of attention by many reseachers in graph theory. For example, as a classical result, K. Corr\'{a}di and A. Hajnal \cite{CH} determined a sharp minimum degree condition for a graph to be the member of $\mathcal{F}(k)$. For $k\ge 1$, let $\mathcal{\bar{F}}(k)=\mathcal{F}(0)-\mathcal{F}(k)$. By definition, note that $\mathcal{\bar{F}}(1)$ is a family of forests. The famous Erd\H{o}s-P\'{o}sa theorem states that there is a number $f(k)=O(k\cdot \log k)$ such that any graph $G$ is a member of $\mathcal{F}(k)$ or $G$ has a set $S$ of $f(k)$ vertices such that that $G-S\in \mathcal{\bar{F}}(1)$. Characterizing $\mathcal{\bar{F}}(k)$ seems an interesting and important problem. A characterization of $\mathcal{\bar{F}}(2)$ is known (see the book \cite{BB}, and also see Theorem~\ref{C} in section 2 as a weaker version). As a related topic, characterizing graphs with no two odd cycles due to Lov\'{a}sz (see the book \cite{S}) is well known. According to the result, one of such graphs can be, roughly, embedded into the projective plane, and it appears in many contexts. But so far we do not know any characterization concerning $\mathcal{\bar{F}}(k)$ with $k\ge 3$. In general, it seems a difficult problem. So, along a different line such as Corr\'{a}di-Hajnal's result, some sufficient conditions for a graph to be a member of $\mathcal{F}(k)$ have been considered. In this paper, we mainly focus on the case $k=3$. We will consider the above problem in view of a Ramsey-type concept. To state this, we need some more definitions. Let $K_n$ be the complete graph of order $n$. Also, let $P_n, C_n$ be a path, a cycle, of order $n$, respectively. For any positive integers $s\ge 2$ and $t\ge 2$, the Ramsey number $R(s,t)$ is defined as the smallest value of $n$ for which every red-blue coloring of $K_n$ yields a red $K_s$ or a blue $K_t$. As an extension of this concept, for arbitrary two graphs $X,Y$, let $r(X,Y)$ be the smallest value of $n$ for which every red-blue coloring of $K_n$ yields a red $X$ or a blue $Y$. In general, determining $R(s,t)$ or $r(X,Y)$ is a very difficult problem. So far, many works have been done for the study of a wide variety of Ramsey-type numbers. As for those numerous results in this field, see the survey \cite{SR}. Now we further generalize the concept of Ramsey numbers as follows. Let $\mathcal{F}, \mathcal{G}$ be families of some fixed graphs such that $\mathcal{F}=\{F_1,\ldots ,F_l\}, \mathcal{G}=\{G_1, \ldots ,G_m\}$. Here $\mathcal{F}$ or $\mathcal{G}$ can be a family having infinitely many elements. We define \textit{the generalized Ramsey number} $r(\mathcal{F}, \mathcal{G})$ as the smallest value of $n$ for which every red-blue coloring of $K_n$ yields a red $F_i \in \mathcal{F}$ or a blue $G_j\in \mathcal{G}$ for some $i,j$. Thus we can regard $R(s,t)$ as the special case of $r(\mathcal{F}, \mathcal{G})$ by letting $\mathcal{F}=\{K_s\}, \mathcal{G}=\{K_t\}$. When $\mathcal{F}$ or $\mathcal{G}$ consists of just one component, say, $\mathcal{G}=\{G\}$, we denote $r(\mathcal{F}, \mathcal{G})$ by $r(\mathcal{F},G)$. By definition, note that $r(\mathcal{F}, \mathcal{G})\le r(\mathcal{F^*}, \mathcal{G^*})$ holds for any subfamilies $\mathcal{F^*}\subset \mathcal{F}, \mathcal{G^*}\subset \mathcal{G}$. In this paper, we consider the case where $\mathcal{F}=\mathcal{F}(k)$ and $\mathcal{G}=\{K_t\}$ for $k\ge 1, t\ge 2$. In \cite{Enomoto}, it is proved that $2t+3k-4\le r(\mathcal{F}(k),K_t)\le k(t-1)+2$ for $k\ge3, t\ge 7$, and when $t\le 6$ or $1\le k\le 2$, $r(\mathcal{F}(k),K_t)=2t+3k-4$ holds. The lower bound is shown by the observation from the graph $G=(t-2)K_2\cup K_{3k-1}$. Our purpose of this paper is to determine $r(\mathcal{F}(3),K_t)$ for all $t\ge 2$. We obtained the following:\\ \textbf{Main Theorem.} $r(\mathcal{F}(3),K_t)=2t+5$ holds for all $t\ge 2$. \\ This result says that $r(\mathcal{F}(k),K_t)=2t+3k-4$ holds for $k=3$, showing that the lower bound of \cite{Enomoto} is the right value. So, one might guess that $r(\mathcal{F}(k),K_t)=2t+3k-4$ holds for all $k,t$. However, this is not true. In fact, it is also proved in \cite{Enomoto} that for any integer $c>0$, there exist $k,t$ such that $r(\mathcal{F}(k),K_t)>c(t+k-1)$. However, the proof is based on a famous theorem due to Erd\H{o}s whose proof depends on a probabilistic method. So we do not see which pairs $k,t$ satisfy $r(\mathcal{F}(k),K_t)> 2t+3k-4$. As mentioned above, it is known that $r(\mathcal{F}(k),K_t)=2t+3k-4$ holds for $t\le 6$. The proof essentially depends on utilizing small Ramsey numbers $R(s,t)$. Since determining $R(s,t)$ is very difficult in general, I guess that determining $r(\mathcal{F}(k),K_t)$ for general $k,t$ would be much more difficult. Actually, even in this specific case where $k=3$, as we will observe in the following sections, the proof depends on many classical and deep results, and it requires us a complicated argument. Moreover, this work is linked with the following further research in this area. Let $K_4^-$ denote the graph obtained from $K_4$ by deleting one edge. A graph which is a subdivision of $K_4^-$ is called \textit{a theta graph}. By the structure, note that every theta graph contains an even cycle. Here we define $\mathcal{F'}(k), \mathcal{G}(k)$ as follows: \begin{center}$\mathcal{F'}(k)=\{ H |\ $ $H$ is a graph which contains $k$ vertex-disjoint even cycles $\ \}$, \\ $\mathcal{G}(k)=\{ H |\ $ $H$ is a graph which contains $k$ vertex-disjoint theta graphs $\ \}$. \end{center} In \cite{FC}, the authors investigate the generalized Ramsey numbers $r(\mathcal{F'}(k), K_t)$ and $r(\mathcal{G}(k), K_t)$, and determine both of them for the cases $k\le 3$ or $t\le 6$. Since $\mathcal{G}(k)\subset \mathcal{F}'(k)\subset \mathcal{F}(k)$, it follows that $r(\mathcal{F}',K_t)\le r(\mathcal{G}(k),K_t)$. Somewhat surprisingly, it is proved that $r(\mathcal{F'}(k), K_t)=r(\mathcal{G}(k), K_t)=3t+4k-6$ holds for $k\le 3$ or $t\le 6$. For the general value of $r(\mathcal{F'}(k), K_t)$ or $r(\mathcal{G}(k), K_t)$, the lower bound is shown by the observation from the graph $G=(t-2)K_3\cup K_{4k-1}$. Hence, we see from these results together with our main theorem and the earlier results in \cite{Enomoto} that excluding odd cycles from the family $\mathcal{F}(k)$ yields quite a big difference of the values of the generalized Ramsey numbers because we have $2t+3k-4=r(\mathcal{F}(k),K_t)<3t+4k-6=r(\mathcal{F'}(k), K_t)=r(\mathcal{G}(k), K_t)$ for small $k$ or $t$. Since the existence of $t,k$ which satisfy $2t+3k-4\alpha (G)$ for any edge $e\in E(G)$, where $\alpha (G)$ means the independence number of $G$. From this definition, note that for any edge $e=xy\in E(G)$, there is an independent set $I$ in $G-e$ such that $|I|=\alpha (G)+1$ and $\{x,y\}\subset I$, and moreover, it is easy to see that a graph which contains multiple edges is not $\alpha$-critical because the deletion of a multiple edge does not affect the independence number of the graph. So far, there are some results known concerning $\alpha$-critical graphs. It is known that every $\alpha$-critical graph $G$ with no isolated vertices has at least $2\alpha (G)$ vertices. In \cite{A}, the following is proved: \begin{thm}[\cite{A}]\label{A} Let $G$ be a connected $\alpha$-critical graph with $|V(G)|=2\alpha (G)+i$ for $i=0,1,2$. Then following statements hold: \begin{enumerate} \item[{(i)}] If $i=0$, then $G\cong K_2$. \item[{(ii)}] If $i=1$, then $G$ is an even subdivision of $K_3$ (i.e., $G$ is an odd cycle). \item[{(iii)}] If $i=2$, then $G$ is an even subdivision of $K_4$. \end{enumerate} \end{thm} Also, for a connected $\alpha$-critical graph $G$ with $|V(G)|=2\alpha (G)+3$, Q. Zhu gave a characterization in \cite{SF}. In order to prove the Main Theorem, a connected $\alpha$-critical graph with no two vertex-disjoint cycles is important. So we shall introduce Zhu's result in the following form: \begin{thm}[\cite{SF}]\label{SF} If $G$ is a connected $\alpha$-critical graph with $|V(G)|=2\alpha (G)+3$ such that $G$ does not contain two vertex-disjoint cycles, then $G$ is an even subdivision of $K_5$. \end{thm} Theorem~\ref{SF} plays an important role in the proof of our main result. (Since Zhu's paper was hard to get, I proved this theorem independently. The preprint is available upon request.) As a related basic fact, we introduce the following remark. This will also be used in the proof of our main result. \\ \noindent\textbf{Remark A.} \textit{Let $G$ be a graph and let $K, P$ be two vertex-disjoint subgraphs in $G$ such that $K$ is a subdivision of $K_5$ and $P=p_1p_2\ldots p_t (t\ge 1)$ is a path. If $|E(V(K),V(P))|\ge 2$, then $\langle V(K)\cup V(P)\rangle$ contains two vertex-disjoint cycles.} \proof{It is easy to check. }\qe In the rest of this section, we list some other known results which will be used in proving the main theorem. Here, some results in $\cite{Enomoto}$ are repeatedly introduced (Theorem~\ref{Eno}) for the convenience of readers. Since the argument after this section goes by using some results concerning the independence number of a graph, each statement in a result will always be rewritten in accordance with the viewpoint not from the Ramsey number but from the independence number of a graph. \begin{thm}[\cite{Lov2},\cite{Dirac2}]\label{C} Suppose that $G$ does not contain two vertex-disjoint cycles and $\delta (G)\ge 3$. Then, one of the followings holds: \begin{enumerate} \item[{(i)}] $G\cong K_5$. \item[{(ii)}] $G$ is a wheel (i.e., $G=K_1+C_l$ where $l\ge 3$). \item[{(iii)}] $G$ is a graph obtained from $K_{3,|V(G)|-3}$ with any set of edges connecting vertices in the $3$-element class added. \end{enumerate} \end{thm} \begin{thm}[\cite{Berge}]\label{D} Every connected $\alpha$-critical graph with at least three vertices is $2$-connected. \end{thm} \begin{thm}[\cite{Enomoto}]\label{Eno} Let $G$ be a graph with $|V(G)|\ge 2\alpha (G)+4$. Then $G$ contains two vertex-disjoint cycles. Moreover, when $\alpha (G)\le 5$ and $|V(G)|\ge 2\alpha (G)+7$, $G$ contains three vertex-disjoint cycles. \end{thm} Combining Theorems~\ref{SF},\ref{D} and~\ref{Eno}, we obtain the following fact: \\ \noindent\textbf{Remark B.} \textit{Let $G$ be an $\alpha$-critical graph with $|V(G)|=2\alpha (G)+3$. If $G$ does not contain two vertex-disjoint cycles, then $G$ consists of the set $U$ of independent edges and an even subdivision of $K_5$. (Here, it is possible that $U=\emptyset$.)} \proof{Suppose that $G$ contains an isolated vertex, say, $v\in V(G)$. Since $\alpha (G-v)=\alpha (G)-1$, it follows that $|V(G-v)|=2\alpha (G)+2=2\alpha (G-v)+4$. However, then by Theorem~\ref{Eno}, $G-v$ (and hence $G$) contains two vertex-disjoint cycles, a contradiction. Thus we see that there is no isolated vertex in $G$. Let $U_1,\ldots ,U_t$ be components of $G$ with $|V(U_1)|\le \ldots \le |V(U_t)|$. If $t=1$, then the assertion immediately follows from Theorem~\ref{SF} as $U=\emptyset$. If $t\ge 2$, then by Theorem~\ref{D}, $U_1,\ldots ,U_{t-1}$ must be independent edges because $G$ does not contain two vertex-disjoint cycles. Putting $U=\{U_1, \ldots , U_{t-1}\}$, we can easily see from Theorem~\ref{SF} that $U_t$ is an even subdivision of $K_5$. }\qe Also, in section 6, the following fact will be used.\\ \noindent\textbf{Remark C.} \textit{Let $G$ be a graph with $|V(G)|=5$. If $|E(G)|\ge 5$, then $G$ contains $P_4$. } \proof{It is easy to check. }\qe \section{Proof of the Main Theorem} In order to prove the main theorem, it suffices for us to prove the following proposition (to see this, put $t=\alpha (G)+1$ below).\\ \noindent\textbf{Proposition.}\ \ \textit{Let $G$ be a graph of order $|V(G)|=2\alpha (G)+7$. Then $G$ contains three vertex-disjoint cycles. } \proof{The proof goes by induction on $\alpha (G)$. By Theorem~\ref{Eno}, we may assume that $\alpha (G)\ge 6$. Suppose that $G$ contain a triangle $T$. Since $\alpha (G-T)\le \alpha (G)$ and $|V(G-T)|=2\alpha (G)+4$, again by Theorem~\ref{Eno}, we can easily find three vertex-disjoint cycles in $G$. Hence in the following argument, we may assume that \begin{center} $G$ does not contain a triangle. \end{center} (We use this assumption as a matter of course.) Suppose that $G$ has an isolated vertex $v$. Then, $\alpha (G-v)=\alpha (G)-1$ holds. Since $|V(G-v)|=2(\alpha (G)-1)+8$, by the induction hypothesis, we can find three vertex-disjoint cycles in $G-v$, which can be the desired cycles in $G$. So, we may assume that $G$ has no isolated vertex. %Also, arguing similarly, we can assume that \\ %for any vertex $v$, there exists a maximum independent set $I$ in $G$ such that $v\notin I$. \hfill (1)\\ Suppose that $G$ has a vertex $v$ such that $d_G(v)=1$ and let $u$ be a vertex with $uv\in E(G)$. It is easy to see that for every maximum independent set $I$ in $G$ (i.e., $|I|=\alpha (G)$), $I\cap \{u,v\}\neq\emptyset$. This means that $\alpha (G-\{u,v\})=\alpha (G)-1$. Since $|V(G-\{u,v\})|=2(\alpha (G)-1)+7$, by the induction hypothesis, we can find three vertex-disjoint cycles in $G-\{u,v\}$, which can be the desired cycles in $G$. Thus we may assume that $\delta (G)\ge 2$. Suppose that there exists a vertex $v$ with $d_G(v)=2$. Let $u,w$ be the vertices such that $N_G(v)=\{u,w\}$. Since $G$ does not contain a triangle, note that $uw\notin E(G)$. Let $G^*$ be a graph obtained from $G$ by contracting edges $uv,wv\in E(G)$. Let $v^*$ be a vertex in $G^*$ which comes from the path $uvw$ in $G$ by the contraction. Suppose that $\alpha (G^*)=\alpha (G)$, and let $I^*$ be a maximum independent set in $G^*$. Let $I'$ be an independent set in $G$ which comes from $I^*-v^*$ in $G^*$. So we have $|I'|\ge \alpha (G)-1$. Then $\{u,w\}\cup I'$ is an independent set in $G$ with $|\{u,w\}\cup I'|> \alpha (G)$, a contradiction. Thus we have $\alpha (G^*)\le\alpha (G)-1$. Since $|V(G^*)|=2\alpha (G)+5=2( \alpha (G)-1)+7\ge 2\alpha (G^*)+7$, by the induction hypothesis, we can find three vertex-disjoint cycles in $G^*$, which implies that $G$ contains three vertex-disjoint cycles. Hence, in the following argument, we may assume that $\delta (G)\ge 3$. Take a cycle $C$ in $G$, and let $H=G-C$. Also, put $V_3:=\{v\in V(G)\ |\ d_G(v)=3\}$. We may assume that $C$ is chosen so that $|V(C)|$ is as small as possible, and subject to the condition, $|V(C)\cap V_3|$ is as large as possible. Since $G$ does not contain a triangle, we have $|V(C)|\ge 4$. Also, by the minimality of $|V(C)|$, we see that $C$ has no chord. Throughout the rest of the proof, set $M:=\{v\in V(H)| \ v\in V_3, E(v,V(C))\neq\emptyset \ \}$. We divide the proof into the following three cases.\\ Case 1: The case where one of the followings holds: \begin{enumerate} \item[{(i)}] $|V(C)|\ge 7$. \item[{(ii)}] $|V(C)|=6$ and $|V(C)\cap V_3|\le 2$. \item[{(iii)}] $|V(C)|=5$ and $V(C)\cap V_3=\emptyset$. \end{enumerate} Case 2: $|V(C)|=6$ and $|V(C)\cap V_3|\ge 3$, or $|V(C)|=5$ and $V(C)\cap V_3\neq\emptyset$. \\ Case 3: $|V(C)|=4$.\\ By the minimality of $|V(C)|$, note that if $|V(C)|\ge 5$, then for any $v\in V(H)$, $|E(v,V(C))|\le 1$, and if $|V(C)|=4$, then for any $v\in V(H)$, $|E(v,V(C))|\le 2$. This means that $\delta (H)\ge 2$ holds for Cases 1 and 2, and $\delta (H)\ge 1$ holds for Case 3. \\ \section{Proof of Case 1} Case 1: The case where one of the following statements holds: \begin{enumerate} \item[{(i)}] $|V(C)|\ge 7$. \item[{(ii)}] $|V(C)|=6$ and $|V(C)\cap V_3|\le 2$. \item[{(iii)}] $|V(C)|=5$ and $V(C)\cap V_3=\emptyset$. \end{enumerate} First we prove the following two claims. \begin{clm}~\label{no2ten} The graph $\langle M\rangle$ has no edge. \end{clm} \proof{ Let $x,y\in M$. Suppose that $xy\in E(G)$. Then, by the assumption of Case 1, we can easily find a cycle $C'$ such that $|V(C')|<|V(C)|$ in $\langle \{x,y\}\cup V(C)\rangle$, or $|V(C')|=|V(C)|$ and $|V(C')\cap V_3|>|V(C)\cap V_3|$. This contradicts the choice of $C$. }\qe \begin{clm}~\label{k13} Let $X$ be a subgraph in $H$ such that $X\cong K_{1,3}$ and let $a\in V(X)$ be the central vertex of $K_{1,3}$. Then $V(X-a)-V_3\neq\emptyset$. \end{clm} \proof{Suppose not. Then, we can easily find a cycle $C'$ such that $|V(C')|<|V(C)|$ in $\langle V(X)\cup V(C)\rangle$, or $|V(C')|=|V(C)|$ and $|V(C')\cap V_3|>|V(C)\cap V_3|$ because for each vertex $b\in V(X-a), E(b,V(C))\neq\emptyset$ and $b\in V_3$. This contradicts the choice of $C$. }\qe Since $\delta (H)\ge 2$, we may assume that $H$ is connected (because if $H$ consists of more than one component, it follows from $\delta (H)$ that $H$ contains two vertex-disjoint cycles). By the definition of $M$, notice that for every vertex $x\in M$, $x$ has degree $2$ in $H$. \begin{clm}~\label{m} For any two vertices $x,y\in M$, $|N_G(x)\cap N_G(y)|\le 1$. \end{clm} \proof{Otherwise, we can find a cycle of length $4$, which contradicts the choice of $C$. }\qe Now we construct a graph $H'$ from $H$ by the following operations: \\ \noindent\textbf{Operation:} \begin{enumerate} \item[{$\bullet$}] For a path $P=xyz$ in $H$ such that $M\cap V(P)=\{y\}$, delete $y$ and join $x$ to $z$ by a new edge. \end{enumerate} Repeat this operation until all the vertices of $M$ are deleted. Let $H'$ be the resulting graph. Then we have $\delta (H')\ge 3$. Note that in view of Claim~\ref{m}, $H'$ does not contain a multiple edge. Apply Theorem~\ref{C} to $H'$. Then we have one of the following cases: \begin{enumerate} \item[{(i)}] $H'\cong K_5$. \item[{(ii)}] $H'$ is a wheel (i.e., $H'=K_1+C_l$ where $l\ge 3$). \item[{(iii)}] $H'$ is a graph with $|V(H')|\ge 6$ obtained from $K_{3,|V(H')|-3}$ with any set of edges connecting vertices in the $3$-element class added. \end{enumerate} In view of the structure of $H'$, let us observe that $H$ is a subdivision of $H'$. Moreover, note that when we obtain $H$ from $H'$, each edge of $H'$ is subdivided by at most one vertex because $\langle M\rangle$ consists of isolated vertices (by Claim~\ref{no2ten}). In the following argument, we divide the proof into two cases: \\ Subcase 1.1: $H'$ contains a wheel as a spanning subgraph(i.e., we deal with both (i) and (ii) in above cases for $H'$ all together).\\ Let $v$ be a vertex in $H-M$ such that $v$ is a vertex which corresponds to a central vertex in $H'$. In view of Claims~\ref{no2ten} and~\ref{k13}, we see that there exists a vertex $u$ in $H-M$ such that $uv\in E(G)$ and there exists a cycle $C'$ such that $|V(C')|\le 5$ and $u,v\in V(C')$. Then we have either $|V(C')|<|V(C)|$ or, $|V(C')|=|V(C)|$ and $|V(C')\cap V_3|>|V(C)\cap V_3|$. This contradicts the choice of $C$. This completes the proof of Subcase 1.1. \\ Subcase 1.2: $H'$ is a graph with $|V(H')|\ge 6$ obtained from $K_{3,|V(H')|-3}$\\ \hfill with any set of edges connecting vertices in the $3$-element class added. \\ \begin{clm}~\label{newclm} In $H$, $|E(v,M)|\le2$ for every $v\in V(H)-M$. \end{clm} \proof{ Suppose there exists a vertex $v\in V(H)-M$ such that $|E(v,M)|\ge 3$. Then, there exists a subgraph $X$ such that $X\cong K_{1,3}, X-v\subset M$ and $v$ is a central vertex of the $K_{1,3}$. Since $M\subset V_3$, this contradicts Claim~\ref{k13}. }\qe In view of Claim~\ref{newclm} and the construction of $H'$, it is easy to check that $|M|\le 6$. First suppose that $|V(H')|=6$. Hence, by the construction of $H'$, we have $|V(H)|=|V(H')|+|M|\le 12$. Then one can easily find a cycle of order less than $7$ in $H$ (a graph obtained from $K_{3,3}$ by subdividing edges with at most $6$ vertices). On the other hand, $19\le 2\alpha (G)+7=|V(G)|\le 12+|V(C)|$, and hence $|V(C)|\ge 7$. This contradicts the minimality of $|V(C)|$. Thus we may assume that $|V(H')|\ge 7$. Let $v_1,v_2,v_3$ be vertices in $H$ such that $d_H(v_i)\ge 4$ for $i=1,2,3$ (i.e., each $v_i$ corresponds to a vertex in the $3$-element class of $H'$). By Claim~\ref{newclm}, there exist two vertices $u_1,u_2$ in $H-M$ such that $u_1,u_2\in N_G(v_1)$ and $d_H(u_i)=3$ for $i=1,2$. Then, from the structure of $H$, there exists a cycle $C'$ such that $|V(C')|\le 6$ and $\{v_1,v_2,u_1,u_2\}\subset V(C')$. By the choice of $C$, we may assume that $|V(C')|\ge 5$. Note that then we have $V(C')\cap M\neq\emptyset$ (i.e., $V(C')\cap V_3\neq\emptyset$). If $|V(C')|=5$, then by replacing $C$ by $C'$, we get a contradiction to the choice of $C$ because $V(C')\cap V_3\neq\emptyset$. So we may assume that $|V(C')|=6$. This means that there exist two vertices $x,y\in M$ such that $x\in N_G(v_2)\cap N_G(u_1), y\in N_G(v_2)\cap N_G(u_2)$. By the symmetry of the roles of $v_2$ and $v_3$, we see that there exist two vertices $x',y'\in M$ such that $x'\in N_G(v_3)\cap N_G(u_1), y'\in N_G(v_3)\cap N_G(u_2)$. Then we can easily find a cycle of length $4$ in $\langle V(H)-\{v_1,u_1,u_2\}\rangle$. This contradicts the minimality of $|V(C)|$. This completes the proof of Subcase 1.2, and this completes the proof of Case 1. \qe \section{Proof of Case 2} Case 2: $|V(C)|=6$ and $|V(C)\cap V_3|\ge 3$, or $|V(C)|=5$ and $V(C)\cap V_3\neq\emptyset$.\\ Here, we further divide the proof into two cases:\\ Subcase 2.1: $|V(C)|=6$ and $|V(C)\cap V_3|\ge 3$. \\ By the assumption that $|V(C)\cap V_3|\ge 3$, we may assume that there exist two vertices $p,q\in V(C)\cap V_3$ such that $pq\notin E(G)$. Put $N_G(p)\cap V(H)=\{p'\}, N_G(q)\cap V(H)=\{q'\}$. By the minimality of $|V(C)|$, we see that $N_G(p)\cap N_G(q)=\emptyset$, and hence $p'\neq q'$. Let us observe that $\alpha (H-\{p',q'\})\le \alpha (G)-2$ because $\{V(H-\{p',q'\})\cup \{p,q\}\}$ forms an independent set. If $\alpha (H-\{p',q'\})\le \alpha (G)-3$, then $|V(H-\{p',q'\})|=2\alpha (G)-1=2(\alpha (G)-3)+5\ge 2\alpha (H-\{p',q'\})+5$. This implies that $H-\{p',q'\}$ contains two vertex-disjoint cycles, and then $G$ contains three vertex-disjoint cycles. So we have $\alpha (H-\{p',q'\})=\alpha (G)-2$. Put $H^*=H-\{p',q'\}$. Let $H^{**}$ be a spanning subgraph of $H^{*}$ such that $H^{**}$ is an $\alpha$-critical graph with $\alpha (H^{*})=\alpha (H^{**})$. Note that $|V(H^{*})|=|V(H^{**})|$ and $\alpha (H^{**})=\alpha (G)-2$. Since $|V(H^{**})|=2\alpha (H^{**})+3$, by Remark B, $H^{**}$ consists of the set $U$ of independent edges (possibly, $U=\emptyset$) and an even subdivision of $K_5$. Here, let us consider the structure $H$. Let $K$ be a subgraph of $H$ such that $K$ is a subdivision of $K_5$. Since $H$ is connected and $|E(x,V(C))|\le 1$ for any $x\in V(H)$, we see that $\langle V(U)\cup \{p',q'\}\rangle$ contains a path $P$ such that $|E(V(P), V(K))|\ge 2$. Then, by Remark A, there exist two vertex-disjoint cycles in $H$, and hence $G$ contains three vertex-disjoint cycles. \\ This completes the proof of Subcase 2.1. \\ Subcase 2.2: $|V(C)|=5$ and $V(C)\cap V_3\neq\emptyset$. \\ Take $p\in V(C)\cap V_3$ and put $N_G(p)\cap V(H)=\{p'\}$. Since $|V(H)|=2\alpha (G)+2$, by Theorem~\ref{Eno}, it is easy to check that $\alpha (H)=\alpha (G)$ and $\alpha (H-p')=\alpha (G)-1$. (To see this, repeat the similar argument in Subcase 2.1.) Similarly as in Subcase 2.1, put $H^*=H-p'$ and let $H^{**}$ be a spanning subgraph of $H^{*}$ such that $H^{**}$ is an $\alpha$-critical graph with $\alpha (H^{*})=\alpha (H^{**})$. Note that $|V(H^{*})|=|V(H^{**})|$ and $\alpha (H^{**})=\alpha (G)-1$. Since $|V(H^{**})|=2\alpha (H^{**})+3$, by Remark B, $H^{**}$ consists of the set $U$ of independent edges (possibly, $U=\emptyset$) and an even subdivision of $K_5$. Here, consider the structure $H$. Let $K$ be a subgraph of $H$ such that $K$ is a subdivision of $K_5$. Since $H$ is connected and $|E(x,V(C))|\le 1$ for any $x\in V(H)$, we see that $\langle V(U)\cup \{p'\}\rangle$ contains a path $P$ such that $|E(V(P), V(K))|\ge 2$. Then, by Remark A, there exist two vertex-disjoint cycles in $H$, and hence $G$ contains three vertex-disjoint cycles. \\ This completes the proof of Subcase 2.1, and hence this completes the proof of Case 2 \qe \section{Proof of Case 3} Case 3: $|V(C)|=4$.\\ Throughout the proof of Case 3, set $C=c_1c_2c_3c_4c_1$. Suppose that $V(C)\cap V_3\neq\emptyset$ and let $p\in V(C)\cap V_3$ and $p'\in N_G(p)\cap V(H)$. Since $E(p,V(H-p'))=\emptyset$, it is easy to see that $\alpha (H-p')\le \alpha (G)-1$. Then, it follows that $|V(H-p')|=2(\alpha (G)-1)+4\ge 2\alpha (H-p')+4$. Hence, by Theorem~\ref{Eno}, $H-p'$ contains two vertex-disjoint cycles, and hence $G$ contains three vertex-disjoint cycles. Thus, in the following argument, we may assume that $V(C)\cap V_3=\emptyset$. Using this assumption, we prove the following claim. \begin{clm}~\label{jisuu} $\delta (H)\ge 2$. \end{clm} \proof{ Let $v$ be a vertex in $H$ such that $|E(v,V(C))|\ge 2$. If $v\in V_3$, then we can find a cycle $C'$ such that $|V(C')|\le 4$ and $|V(C')\cap V_3|>|V(C)\cap V_3|$ in $\langle \{v\}\cup V(C)\rangle$, which contradicts the choice of $C$. Thus $d_G(v)\ge 4$ holds. This implies $\delta (H)\ge 2$. }\qe Let $H^{*}$ be a spanning subgraph of $H$ such that $H^{*}$ is an $\alpha$-critical graph with $\alpha (H)=\alpha (H^{*})$. Note that $|V(H)|=|V(H^{*})|$ and $\alpha (H^{*})=\alpha (G)$. Since $|V(H^{*})|=2\alpha (H^{*})+3$, by Remark B, $H^{*}$ consists of the set $U$ of independent edges (possibly, $U=\emptyset$) and an even subdivision of $K_5$. In view of Remark A and Claim~\ref{jisuu}, it is easy to see that $U=\emptyset$ (because, if $U\neq\emptyset$, there exists a path $P$ in $U$ such that $P$ sends at least two edges to the subdivided $K_5$ in $H$ and then Remark A can be applied to $H$) and $H$ is isomorphic to an even subdivision of $K_5$. \begin{clm}~\label{no4ten} Let $P=p_1p_2p_3p_4$ be a path of length $3$ in $H$. Then $V(P)-M\neq\emptyset$. \end{clm} \proof{Otherwise, we can find a cycle $C'$ in $\langle V(C)\cup V(P)\rangle$ such that $|V(C')|=3$ or $|V(C')|=4$ and $V(C')\cap V_3\neq\emptyset$, which contradicts the choice of $C$. }\qe In view of Claim~\ref{no4ten}, we see that $H$ is obtained from $K_5$ by subdividing each edge with at most two vertices. Since $\alpha (G)\ge 6$, this implies that $H$ is obtained from $K_5$ by subdividing at least $5$ edges and for each subdivision of an edge in $H$, two vertices of $M$ is contributed. Hence, in view of Remark C, it is easy to check that there is a path $P=p_1p_2\ldots p_8$ in $H$ such that $H-P$ contains a cycle and $M\cap V(P)=\{p_1,p_2,p_4,p_5,p_7,p_8\}$. By the assumption that $V(C)\cap V_3=\emptyset$, note that there is no cycle of order $4$ which contains a vertex in $\{p_1,p_2,p_4,p_5,p_7,p_8\}$ (because of the choice of $C$). So, by symmetry, we may assume that $p_1c_1,p_2c_3\in E(G)$. Suppose that $E(\{p_4,p_5\},\{c_1,c_3\})\neq\emptyset$. By the choice of $C$, this forces $p_4c_1,p_5c_3\in E(G)$. However, since $E(\{p_7,p_8\},\{c_2,c_3,c_4\})\neq\emptyset$, we can find two vertex-disjoint cycles in $\langle V(P)\cup V(C)\rangle$. Hence we may assume that $E(\{p_4,p_5\},\{c_1,c_3\})=\emptyset$. By symmetry, we may assume that $p_4c_2,p_5c_4\in E(G)$ (because $p_4$ can not be adjacent to $c_1$ by the choice of $C$). By the same reason, we see that $p_7$ can not be adjacent to $c_4$. This forces $E(\{p_7,p_8\},V(C))=\{p_7c_2,p_8c_4\}$ or $E(\{p_7,p_8\},V(C))=E(\{p_7,p_8\},\{c_1,c_3\})$. In any case, we can easily find two vertex-disjoint cycles in $\langle V(P)\cup V(C)\rangle$. Hence $G$ contains three vertex-disjoint cycles. This completes the proof of Case 3, and this completes the proof of Proposition. } \qe This completes the proof of the Main Theorem.\qe \section{Concluding remarks} As noted before, $r(\mathcal{F}, \mathcal{G})\le r(\mathcal{F^*}, \mathcal{G^*})$ holds for any subfamilies $\mathcal{F^*}\subset \mathcal{F}, \mathcal{G^*}\subset \mathcal{G}$. Define $\mathcal{F^*}(k)$ as follows: \begin{center} $\mathcal{F^*}(k)=\{ C_1\cup C_2\cup\ldots C_k|\ $ each $C_i$ is a cycle $\}$. \end{center} By definition, we have $\mathcal{F^*}(k)\subset \mathcal{F}(k)$. In fact, the exactly same argument concerning $r(\mathcal{F}(k), K_t)$ can be applied in determining $r(\mathcal{F^*}(k), K_t)$. So we can easily have $r(\mathcal{F^*}(k),K_t)=r(\mathcal{F}(k), K_t)$. \\ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} I would like to thank Dr. Hajime Matsumura who suggested to me the problem discussed in this paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % we recommend using BibTeX to create a bibliography % \bibliographystyle{plain} % \bibliography{myBibFile} % then copy and past the contents of your .bbl file into this .tex file \begin{thebibliography}{99} \bibitem{A} B. Andr\'{a}sfai, On critical graphs, Theory of Gr. Int. Symp. Rome, Dunod, Paris--Gordon and Breach, New York, (1967), 9--19. \bibitem{Berge} C. Berge, Une propri\'et\'e des graphes $k$-stables-critiques, Combinatorial Structures and their applications, Gordon and Breach, New York, (1970), 7--11. %\bibitem{Cat} %P.A. Catlin, Hajos' graph-coloring conjecture: variations and counterexamples, J. Combin. Theory Ser. B, \textbf{26} (1979), 268--274. \bibitem{BB} B. Bollob\'{a}s, Extremal graph theory, Dover Publications Inc. Nineola, New York. (2004). \bibitem{CH} K. Corr\'{a}di, A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar., \textbf{14} (1963), 423--439. \bibitem{Dirac} G.A. Dirac, Homomorphism theorems for graphs, Math. Ann., \textbf{153}(1964), 69--80. \bibitem{Enomoto} Y. Egawa, H. Enomoto, S. Jendrol, K. Ota, I. Schiermeyer, Independence number and vertex-disjoint cycles, Discrete Math., \textbf{307}(2007), 1493--1498. \bibitem{FC}S. Fujita, C. Magnant, Independence number and disjoint theta graphs, Electronic J. Combin., \textbf{18}(2011) P150. \bibitem{hajnal} A. Hajnal, A theorem on $k$-saturated graphs, Canad. Math. J., \textbf{17}(1965), 720--724. \bibitem{Lov2} L. Lov\'asz, On graphs not containing independent circuits, Mat. Lapok., \textbf{16}(1965), 298--299. %\bibitem{Lov} L. Lov\'asz, Combinatorics, Coll. Math. Soc. J. Bolyai, \textbf{1%5}, Bolyai-North-Holland (1977) \bibitem{SR} S.P. Radziszowski, Small Ramsey numbers, Electronic J. Combin., \textbf{DS1}(2006) \#11. \bibitem{S} P.D. Seymour, Matroid minors, Handbook of Combinatorics, Elsevier, Amsterdam \textbf{1} (1995), 527--550. \bibitem{GPW} W. Wessel, Kanten-kritische Graphen mit der Zusammenhangszahl $2$, Manuscripta Math., \textbf{2}(1970), 309--334. \bibitem{Dirac2} B. William G, A new proof of a theorem of Dirac, Canad. Math. Bull., \textbf{8}(1965), 459--463. \bibitem{SF}Q. Zhu, The structure of $\alpha$-critical graphs with $|V(G)|-2\alpha (G)=3$, Graph theory and its applications: East and West (Jinan, 1986), 716--722, Ann. New York Acad. Sci., \textbf{576} (1989). \end{thebibliography} \end{document}