%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Acyclic cutsets % % B L % F P % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P35}{20(1)}{2013} % 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} % we recommend the graphicx package for importing figures \usepackage{graphicx} \usepackage{graphics} \usepackage{tikz} \usetikzlibrary{calc} %\usepackage{pgfmath} % 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 \theoremstyle{plain} \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} %%%%%%%%%%%%%%%%%%%%%%%%%%%% symbols definitions \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\cP{\mathcal{P}} \def\gsc{\mathcal{G}_{sc}} \def\scs{\textsc{stable cutset}} \def\acs{\textsc{acyclic cutset}} %\renewcommand{\theenumi}{\alph{enumi}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title%[Stable Cutsets] {\bf Extremal Graphs Having No Stable Cutsets} \author{Van Bang Le\\ \small Institut f\"ur Informatik\\[-0.8ex] \small Universit\"at Rostock\\[-0.8ex] \small Rostock, Germany\\ \small\tt le@informatik.uni-rostock.de\\ \and Florian Pfender\\ \small Department of Mathematics and Statistics\\[-0.8ex] \small University of Colorado at Denver\\[-0.8ex] \small Denver, CO, U.S.A.\\ \small\tt Florian.Pfender@ucdenver.edu} %\keywords {stable cutset; independent cutset; fragile graph; extremal graph} %\subjclass {} \date{\dateline{Jul 4, 2012}{Feb 6, 2013}{Feb 18, 2013}\\ \small Mathematics Subject Classifications: 05C35, 05C40, 05C69, 05C75} \begin{document} \maketitle \begin{abstract} A stable cutset in a graph is a stable set whose deletion disconnects the graph. It was conjectured by Caro and proved by Chen and Yu that any graph with $n$ vertices and at most $2n-4$ edges contains a stable cutset. The bound is tight, as we will show that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. As a by-product, an algorithmic implication of our result will be pointed out. \bigskip\noindent \textbf{Keywords:} stable cutset; independent cutset; fragile graph; extremal graph \end{abstract} \section{Introduction} All graphs considered are finite and have no loops or multiple edges. For a graph $G=(V(G), E(G))$ with vertex set $V(G)$ and edge set $E(G)$, write $|G|=|V(G)|$ and $\| G\| = |E(G)|$. A \emph{stable set} (or an \emph{independent set}) in $G$ is a set of pairwise non-adjacent vertices. A \emph{cutset} (or \emph{separator}) of $G$ is a set $S$ of vertices such that $G-S$ is disconnected. A \emph{stable cutset} in $G$ is a cutset of $G$ which is also a stable set. Throughout this paper, we consider the empty set as stable. So in particular, every disconnected graph contains a stable cut set. It is naturally expected that graphs with few edges would have stable cutsets. Indeed, the following theorem was conjectured by Caro and proved by Chen and Yu. \begin{theorem}[\cite{ChenYu}]\label{ChenYu} Let $G$ be a graph with $\| G\|\le 2|G|-4$. Then $G$ contains a stable cutset. \end{theorem} Small stable cutsets are discussed in \cite{CFJ}, and algorithmic and complexity aspects of stable cutsets are discussed in \cite{Chvatal,BDLS,KleFig,LMM,LeRand}. The importance of stable cutsets in connection to perfect graphs are demonstrated in~\cite{CorFon,Tucker}. In~\cite{CarYus} it is noted that graphs containing stable cutsets play a role in some decomposition algorithms. Actually, Chen and Yu proved the following stronger result. \begin{theorem}[\cite{ChenYu}]\label{ChenYu2} Let $G$ be $2$-connected a graph with $\| G\|\le 2|G|-4$. Then for every vertex $x\in V(G)$, there is a stable cutset not containing $x$. \end{theorem} This implies immediately the following corollary; a vertex $x$ is a cut vertex if $\{x\}$ is a cutset. \begin{corollary}\label{ChenYu3} Let $G$ be a graph with $\| G\|\le 2|G|-4$, and $x\in V(G)$. Unless $x$ is the unique cut vertex in $G$, there is a stable cutset not containing $x$. \end{corollary} The bound in Theorem \ref{ChenYu} is tight. In the next section we describe all graphs with $n$ vertices and $2n-3$ edges that have no stable cutset (Theorem~\ref{thm:gsc}). In the last section we will point out an algorithmic implication of our result. \medskip \noindent \textbf{Notation and definitions.}\, Let $G$ be a graph. The complement of $G$ is written $\overline{G}$. The neighborhood of a vertex $v$ in $G$, denoted by $N_G(v)$, is the set of all vertices in $G$ adjacent to $v$; if the context is clear, we simply write $N(v)$. Set $\deg(v) = |N(v)|$, the degree of the vertex $v$. For a subset $W \subseteq V (G)$, $N(W)=\bigcup_{w\in W} N(w) \setminus W$, and $G[W]$ is the subgraph of $G$ induced by $W$; write $G -W =G[V(G)\setminus W]$ and $G-w=G-\{w\}$. Given another graph $H$, an $H$-cutset $S$ of $G$ is a cutset such that $G[S]$ is isomorphic to $H$, while a $k$-cutset is a $k$-element cutset. An edge cut of $G$ is a set $M$ of edges such that $G-M=(V(G),E(G)\setminus M)$ is disconnected. A \emph{matching cut} in $G$ is an edge cut of $G$ that is also a matching. $P_k$ stands for the path with $k$ vertices and $k-1$ edges, $C_k$ is the cycle with $k$ vertices and $k$ edges. A complete graph with $k$ vertices is denoted $K_k$; $K_k^-$ is $K_k$ minus an edge. The $K_3$ is also called a triangle and the $\overline{C_6}$ is also called a triangular prism; see Figure~\ref{fig:triangularprism}. \begin{figure}[htb] \begin{center} \begin{tikzpicture}[scale=.4] \tikzstyle{vertex}=[circle,inner sep=1pt,fill=black]; \node[vertex] (a) at (0,0) {}; \node[vertex] (b) at (2,2) {}; \node[vertex] (c) at (0,4) {}; \node[vertex] (d) at (7,0) {}; \node[vertex] (e) at (5,2) {}; \node[vertex] (f) at (7,4) {}; \draw (a) -- (b) -- (c) -- (a); \draw (d) -- (e) -- (f) -- (d); \draw (a) -- (d); \draw (b) -- (e); \draw (c) -- (f); \end{tikzpicture} \caption{The triangular prism $\overline{C_6}$.} \label{fig:triangularprism} \end{center} \end{figure} We will make use of the following well-known graph operation. A clique in a graph is a set of pairwise adjacent vertices. Let $G_1, G_2$ be disjoint graphs which each have nonempty cliques $Q_1$, respectively, $Q_2$ of the same size. A graph obtained from $G_1$ and $G_2$ by first choosing a bijection $f: Q_1 \to Q_2$ and then identifying each $x$ in $Q_1$ with $f(x)$ in $Q_2$ is said to arise from $G_1$ and $G_2$ by clique identification. If the chosen cliques have two, respectively, three vertices, we also speak of \emph{edge identifications}, respectively, \emph{triangle identifications}. Finally, for convenience, we consider $G_1$ and $G_2$ as induced subgraphs of the graph arising from $G_1$ and $G_2$ by clique identification. Thus, a graph $G$ arises from two graphs by clique identification if and only if there exist induced subgraphs $G_1$ and $G_2$ in $G$ such that $G=G_1\cup G_2$ and $G_1\cap G_2$ is a clique. % Conversely, A graph $G$ is an \emph{edge bonding} (respectively, a \emph{triangle bonding}) of two graphs $G_1$ and $G_2$ if $G= G_1 \cup G_2$ and $G_1 \cap G_2$ is an edge (respectively, a triangle). \section{The Result} Let $\gsc$ be the the class of graphs one gets by recursively glueing together triangles and triangular prisms along an edge or triangle. More precisely, \begin{itemize} \item[1.] $K_3\in \gsc$ and $\overline{C_6}\in\gsc$. \item[2.] If $G_1, G_2\in \gsc$ and $G$ is obtained from $G_1$ and $G_2$ by edge identification, then $G\in\gsc$. \item[3.] If $G_1, G_2\in \gsc$ and $G$ is obtained from $G_1$ and $G_2$ by triangle identification, then $G\in\gsc$. \end{itemize} Notice that we may restrict to $G_2\in\{ K_3,\overline{C_6}\}$ in the above definition without changing the class $\gsc$, which effects the complexity of the algorithm considered in the last section of the paper. %Notice: By def. $K_1$ is disconnected. Hence $K_2$ does not belong to \gsc. \begin{proposition}\label{prop:gsc} Any graph $G\in\gsc$ has $\| G\| = 2|G|-3$ edges and no stable cutset. \end{proposition} \begin{proof} The statement is obvious for triangles and triangular prisms. Let $G$ arise from $G_1, G_2\in\gsc$ by edge or triangle identification, and write $G=G_1\cup G_2$ with clique $Q=G_1\cap G_2$ of size two or three. Then \[ |G|=|G_1|+|G_2|-|Q|\quad\text{and}\quad \| G\| = \|G_1\| +\|G_2\| - \| Q\|, \] and hence, by induction, \[ \| G\| = (2|G_1|-3)+(2|G_2|-3) - \| Q\| = (2|G|-3)+(2|Q|-3-\|Q\|) = 2|G|-3. \] Note that, as $Q$ is a clique, any stable cutset in $G$ is also a stable cutset in $G_1$ or $G_2$. Hence, by induction again, $G$ has no stable cutset. \end{proof} \begin{theorem}\label{thm:gsc} Let $G$ be a graph with $\| G\|\le 2|G|-3$. Then $G$ contains a stable cutset or $G\in \gsc$. %can be constructed from triangles and prisms by recursive glueing along an edge or triangle. \end{theorem} \begin{proof} Our proof starts with a number of claims. For the sake of contradiction, we assume that $G$ is a minimal counterexample to Theorem~\ref{thm:gsc}. Then, by Theorem~\ref{ChenYu}, \begin{claim}\label{sc1} $\| G\|= 2|G|-3$. \end{claim} \begin{claim}\label{sc2} Every vertex $v$ lies in a triangle. \end{claim} Otherwise, $N(v)$ would be a stable cutset in $G$. \begin{claim}\label{sc3} $G$ contains no $K_2$-cutset and no $K_3$-cutset. \end{claim} %\emph{Proof of Claim~\ref{sc3}:}\, Otherwise, let $G$ contain a cutset $Q$ isomorphic to $K_2$ or $K_3$. Write $G=G_1\cup G_2$ with $G_1\cap G_2=Q$. Since $G$ has no stable cutset and $Q$ is a clique, $G_1$ and $G_2$ have no stable cutset. By Theorem~\ref{ChenYu}, $\|G_i\|\ge 2|G_i|-3$, $i=1,2$, hence, by Claim~\ref{sc1}, $\|G_i\|= 2|G_i|-3$. Therefore, by the minimality of $G$, $G_i\in\gsc$, and thus $G\in\gsc$, a contradiction. \begin{claim}\label{sc4} $G$ is $3$-connected. \end{claim} Otherwise, by Claim~\ref{sc3}, $G$ would contain a stable cutset. \begin{claim}\label{sc5} $G$ contains no $3$-edge matching cut. \end{claim} %\emph{Proof of Claim~\ref{sc5}:}\, Otherwise, let $M=\{x_1y_1, x_2y_2, x_3y_3\}$ be a matching cut of $G$. Since $G$ is 2-connected, $G-M$ has exactly two components, say $G_1$ and $G_2$. Then the set of all edges between $G_1$ and $G_2$ is exactly $M$, and we may assume that $x_1,x_2,x_3\in V(G_1)$, $y_1,y_2,y_3\in V(G_2)$. Now, if $\{x_1,x_2,x_3\}$ is not a clique, say $x_1x_2\not\in E(G)$, then $\{x_1,x_2,y_3\}$ is a stable cutset of $G$, a contradiction. So, $\{x_1,x_2,x_3\}$ and, by symmetry, $\{y_1,y_2,y_3\}$ are cliques. Since $G\not=\overline{C_6}$, at least one of these cliques must be a cutset of $G$, contradicting Claim~\ref{sc3}. \begin{claim}\label{sc6} $G$ contains no $K_4^-$. \end{claim} Otherwise, contract the edge between the two vertices of degree $3$ in this (not necessarily induced) subgraph, resulting in a graph $G'$. By Claim~\ref{sc4}, $G'$ is 2-connected. By Claim~\ref{sc1}, $\|G'\| \le \|G\|-3 = 2|G|-6=2|G'|-4$. By Theorem~\ref{ChenYu2}, $G'$ contains a stable cutset not containing the new vertex, which is also a stable cutset in $G$. \begin{claim}\label{sc7} For any two non-adjacent vertices $x,y$ we have $|N(x)\cap N(y)|\le 2$. \end{claim} Otherwise, contract the two vertices, and get a ($2$-connected) graph $G'$ with $\| G'\|\le 2|G'|-4$. Then, $G'$ has a stable cutset by Theorem~\ref{ChenYu} which yields a stable cutset in~$G$. \begin{claim}\label{sc8} $G$ contains no $P_3$-cutset. \end{claim} Otherwise, let $\{x,y,z\}$ be a cutset of $G$ such that $xy, yz\in E(G)$, and let $G_1$ and $G_2$ be induced subgraphs of $G$ with $G=G_1\cup G_2$ and $G_1\cap G_2=\{x,y,z\}$. Then \[ \|G_1\|+\|G_2\|=\|G\|+2=2|G|-1=2|G_1|+2|G_2|-7. \] Thus, by symmetry $\| G_1\|\le 2|G_1|-4$, and note that, by Claim~\ref{sc4}, $y$ is not a cut vertex of $G_1$. Therefore, by Corollary~\ref{ChenYu3}, $G_1$ contains a stable cutset not containing $y$. But this is then also a stable cutset in $G$. \begin{claim}\label{sc9} In every triangle, at least two vertices belong to other triangles as well. \end{claim} \emph{Proof of Claim~\ref{sc9}:}\, Assume that $xyz$ is a triangle and $y$ and $z$ are in no other triangles. Then there is an edge $y'z'$ with $y'\in N(y)$ and $z'\in N(z)$ as otherwise, by Claim~\ref{sc6}, $(N(y)\cup N(z))\setminus \{ y,z\}$ is a stable cutset. % $\{y,z\}$ $K_2$-cutset Contracting $\{ y,z'\}$ %(or $\{ y',z\}$) to a new vertex $v$ yields a graph $G'$ with $\| G'\|\le 2|G'|-3$. Since every stable cutset in $G'$ yields a stable cutset in $G$, $G'$ has no stable cutset. So $G'\in\gsc$ by the minimality of $G$. Now assume that $G'$ contains a $3$-edge matching cut $M$. Then by Claim~\ref{sc5}, $v$ is in one of the edges in $M$, say $M=\{au,bv,cw\}$, and further, we have $by',bz\in E(G)$. Let the two triangles in $G'$ enclosing $M$ be $abc$ and $uvw$, where $b\in \{ y',z\}$ by Claim~\ref{sc7}. Let $G_1$ be the component of $G-\{au, by',bz,cw\}$ containing $abc$. By Claim~\ref{sc3}, $G_1=abc$. Let $G_2=G-G_1$, and note that $\|G_2\|=2|G_2|-4$. Further, $G_2$ is $2$-connected as any $1$-cutset in $G_2$ would yield a $2$-cutset in $G$ if we add $b$ to it. We may assume by symmetry that $z'w\in E(G)$ (we will not use the fact that $y$ lies in only one triangle, so $y$ and $z'$ are symmetric in the following argument). Further assume that $yu\in E(G)$. By Theorem~\ref{ChenYu2}, $G_2$ contains a stable cutset $X$ not containing $w$. As $X$ is not a stable cutset of $G$, $y$ is in a different component of $G_2-X$ than $w$. Thus, $u\in X$ and $X\cup \{b\}$ is a cutset of $G$, and as this is not a stable cutset, $z'\in X$. But then $X\cup \{c\}$ is a stable cutset in $G$, a contradiction. So $yu\notin E(G)$ and therefore $z'u\in E(G)$. By Theorem~\ref{ChenYu2}, $G_2$ contains a stable cutset $X$ not containing $z'$, with $y$ and $z'$ in different components of $G_2-X$. But then $X\cup \{b\}$ is a stable cutset in $G$, a contradiction. Therefore, $G'$ contains no $3$-edge matching cut. As a result, $G'$ can be built by starting with a triangle and recursively glueing on triangles along an edge ($G'$ is a so-called $2$-tree). As $G$ is $3$-connected, every such $2$-cutset in $G'$ has the form $uv$, and $u$ is connected to exactly one of $y$ and $z'$ by Claim~\ref{sc8}. Further, every vertex of degree at least $3$ in $G'$ lies in such a cutset. On the other hand, there are at least two vertices of degree $2$ in $G'$. As $G$ is $3$-connected, such vertices must lie in $N_G(y)\cap N_G(z')$, but by Claim~\ref{sc7}, $N_G(y)\cap N_G(z')=\{ y',z\}$. Thus, exactly the two vertices $y'$ and $z$ have degree $2$ in $G'$, and $N_G(z)=\{ x,y,z'\}$. By a symmetric argument using a contraction of $\{y',z\}$ instead of $\{y,z'\}$ in the beginning, $N_G(y)=\{ x,y',z\}$. But this implies that $N_G(z')=V(G)\setminus\{y,z'\}$, as every vertex in $V(G)\setminus \{y,z'\}$ is in $N_{G'}(v)=N_G(y)\cup N_G(z')$. In particular, $xz'\in E(G)$. This contradicts Claim~\ref{sc6}, as $G[\{x,y,z,z'\}]$ is then a $K_4^-$, hence Claim~\ref{sc9} follows. \medskip Consider the vertex-triangle incidence graph $H$ of $G$, i.e., the bipartite graph with partite sets $V(G)$ and the set of all triangles $T(G)$ in $G$, with an edge between a vertex $v\in V(G)$ and a triangle $T\in T(G)$ if $v\in V(T)$. %. On the other hand By Claim~\ref{sc9}, $H$ is not a tree. Let $x_1T_1x_2T_2\ldots x_kT_kx_1$ be a shortest cycle in $H$. By Claim~\ref{sc6}, $H$ has no cycles of length less or equal to $6$, so $k\ge 4$. Then $C=x_1x_2\ldots x_kx_1$ is a cycle in $G$, and $V(T_i)\setminus V(C)$ consists of a distinct vertex for every $1\le i\le k$. %, we call this vertex $y_i$. % By Claim~\ref{sc2}, Claim~\ref{sc9}, and Claim~\ref{sc6}, $G$ has an induced cycle $x_1x_2\ldots x_kx_1$ with (not necessarily all distinct) vertices $y_i\in N(x_i)\cap N(x_{i+1})$ for $1\le i\le k-1$ for some $k\ge 4$. % mehr Begruendung?? If we contract $P=x_1x_2\ldots x_{k-1}$ to a new vertex $v$, we get a graph $G'$ with $\|G'\|\le 2|G'|-4$. If $v$ is not the unique cut vertex of $G'$, then we can use Corollary~\ref{ChenYu3} to find a stable cutset of $G'$ not containing $v$, which is then also a stable cutset of $G$, a contradiction. Thus, $v$ is the unique cut vertex of $G'$. Let $Y$ be a component of $G\setminus V(P)$ and $1\le r\le s\le k-1$, such that \[ \{ x_r,x_s\}\subseteq N(Y)\cap V(P)\subseteq \{ x_r,\ldots,x_s\}, \] and \[ N(Z)\cap V(P)\setminus \{ x_{r+1},\ldots,x_{s-1}\}\ne\emptyset \] for all components $Z$ of $G\setminus V(P)$. Note that $s\ge r+2$ as $G$ is $3$-connected. % by Claim~\ref{sc4}. Now contract $x_{r+1}\ldots x_{s-1}$ to a new vertex $x$ and call the resulting graph $G''$. Then $\|G''\|\le 2|G''|-3$, and let $G_1:=G''[Y\cup \{ x_r, x, x_s\}]$ and $G_2:=G''\setminus Y$. As in Claim~\ref{sc8}, we have \[ \|G_1\|+\|G_2\|=\|G''\|+2\le 2|G''|-1=2|G_1|+2|G_2|-7. \] Further, $x$ is neither a cut vertex of $G_1$ nor of $G_2$. Thus, by Corollary~\ref{ChenYu3}, either $G_1$ or $G_2$ has a stable cutset not containing $x$. But this is also a stable cutset of $G$, a contradiction. \end{proof} \section{Complexity Issues} With \scs\ we mean the following decision problem: \lq Does a given graph admit a stable cutset?\rq\ The computational complexity of \scs\ has been addressed in a number research papers, e.g., \cite{Chvatal,BDLS,KleFig,LMM,LeRand}. To sum up, \scs\ is NP-complete for graphs of maximum degree five (even for $K_4$-free planar graphs with maximum degree five \cite{LMM} and for $5$-regular line graphs of bipartite graphs \cite{LeRand}), and is trivial for graphs of maximum degree three (by Theorem~\ref{ChenYu}, such graphs with more than seven vertices always have a stable cutset). The complexity status of \scs\ is still open for graphs with maximum degree four. By Theorem~\ref{ChenYu}, \scs\ for graphs with maximum degree four remains open only in four cases, namely for graphs with $n$ vertices and $m$ edges where $2n-3\le m\le 2n$. Thus, the following problem is of interest and has been addressed in \cite{LeRand,C5W2003}: \bigskip \noindent \scs $(n, m)$.\, \emph{Given a graph $G$ with $n$ vertices and $m$ edges. Does $G$ have a stable cutset?} \bigskip \noindent It was shown in \cite{LeRand} that, for any given $\epsilon >0$, \scs $(n, m)$ is NP-complete for $m\ge (2+\epsilon)n$. By Theorem~\ref{ChenYu}, \scs $(n, m)$ is trivial for $m\le 2n-4$. By Theorem~\ref{thm:gsc}, we obtain the following: \begin{corollary}\label{cor:2n-3} \scs $(n,2n-3)$ is solvable in polynomial time. \end{corollary} \begin{proof} Let $G$ be a graph with $n$ vertices and $m=2n-3$ edges. Then, by Theorem~\ref{thm:gsc}, $G$ has a stable cutset, or else $G$ must belong to $\gsc$. Since the members of $\gsc$ can be recognized in time $O(n^4)$ in an obvious way, Corollary~\ref{cor:2n-3} follows. In fact, the recognition of $G\in\gsc$ can be performed in quadratic time, based on the following observations. For every edge $xy$, we can in linear time test if $\{x,y\}$ is a cutset and determine the components of $G-\{x,y\}$. If $G\in\gsc$, performing this for all $2n-3$ edges, this process yields in quadratic time a set of at most $n-2$ components with at most a total of $3n-6$ vertices, where each component is obtained from copies of $K_3$ and $\overline{C_6}$ via triangle identification. In particular, every vertex is in exactly one $K_3$. Further, every vertex of degree $2$ is in a $K_3$-component, and the non-separating $K_3$ in other components consist exactly of the vertices of degree $3$. This way, we can easily recover the building blocks, the $\overline{C_6}$, used to build up the components in quadratic time, by cutting off one $\overline{C_6}$ which includes a non-separating $K_3$ at a time (linear time for each step, linear number of steps). With a bit more effort, one can show that one can decide if $G\in\gsc$ in time $O(n\log{n})$, but for the sake of exposition we do not present the argument here. % % If $G\in\gsc$, then $G$ the minimum degree of $G$ is 2 or 3. Moreover, % \begin{enumerate} % \item The neighborhood of any degree 2-vertex is a clique. % \item If $G$ has no degree 2-vertices, then there exists a degree 3-vertex $v$ such that $G[N(v)]$ consists of exactly one edge $xy$ and one isolated vertex $z$, and for all such vertices $v$, % \begin{enumerate} % \item\label{degree-3a} $G[N(v)\cup N(x)\cup N(y)]$ is isomorphic to $\overline{C_6}$ and $\deg(x)=\deg(y)=3$, or %else % \item\label{degree-3b} $G[N(v)\cup N(z)]$ is isomorphic to $\overline{C_6}$ and $\deg(x)=\deg(z)=3$. % \end{enumerate}\label{degree-3} % \end{enumerate} % % Then, the algorithm processes as follows. If $G\in\{K_3, \overline{C_6}\}$, then output \lq yes\rq\ and stop. Otherwise, let $v$ be a degree 2-vertex of $G$ (if any). If $N(v)$ is not a clique, then output \lq no\rq\ and stop, otherwise process recursively on $G-v$. If $G$ has no degree 2-vertices, let $v$ be a vertex with $N(v)=\{x,y,z\}$ as in~\eqref{degree-3}. If such a vertex $v$ does not exist, then output \lq no\rq\ and stop. Now, in case~\eqref{degree-3a}, process recursively on $G-\{v,x,y\}$. In case~\eqref{degree-3b}, let $xvzw$ be the $C_4$ in $G[N(v)\cup N(z)]=\overline{C_6}$ containing $x,v,z$ and process recursively on $G-\{v,x,z,w\}$. Since, the vertex degrees can be computed in $O(n)$, the running time $t(n)$ satisfies $t(n)\le O(n)+t(n-1)$. Note that $t(n)=O(1)$ for $n\le 6$, hence $t(n)=O(n^2)$. \end{proof} %Remark: Clique cutsets in arbitrary graphs can be found in polynomial time (\cite{White}). % A property for graphs $G$ with $m=2n-2$: We may assume that, for every edge $e$, $G-e$ has a stable cutset! But this seems not enough to decide if $G$ has a stable cutset or not \dots % % If in addition $G$ has maximum degree four, we may further assume that, for every vertex $v$, $G-v$ has a stable cutset! \bigskip\bigskip\bigbreak \bibliographystyle{amsplain} \begin{thebibliography}{99} %\bibitem{BM} J.A.~Bondy, U.S.R.~Murphy, \textit{Graph Theory with Applications}, %{\it Macmillan, London} and {\it Elsevier, New York}, 1976. %\bibitem{Boll} B.~ Bollob\'as, ``{\em Modern Graph Theory},'' %Springer Verlag, New York, 1998. \bibitem{BDLS} A. Brandst\"adt, F. Dragan, V.B. Le, T. Szymczak, On stable cutsets in graphs, Discrete Appl. Math. 105 (2000) 39-50. \bibitem{CarYus} Y. Caro, R. Yuster, Decomposition of slim graphs, Graphs Combinatorics 15 (1999) 5-19. \bibitem{CFJ} G. Chen, R.J. Faudree, M.S. Jacobson, Fragile graphs with small independent cuts, J. Graph Theory 41 (2002) 327-341. \bibitem{ChenYu} G. Chen, X. Yu, A note on fragile graphs, Discrete Math. 249 (2002) 41-43. \bibitem{Chvatal} V. Chv\'atal, Recognizing decomposable graphs, J. Graph Theory 8 (1984) 51-53. \bibitem{CorFon} D.G. Corneil, J. Fonlupt, Stable set bonding in perfect graphs and parity graphs, J. Combin. Theory (B) 59 (1993) 1-14. %\bibitem{Diestel} R. Diestel, ``{\em Graph Theory},'' Springer Verlag, Heidelberg, 2005. %\bibitem{Gavril} F. Gavril, Algorithms on separable graphs, Discrete Math. 19 (1977) 159-165. %\bibitem{Kanneko} A.~Kanneko, Problem 26 ``{\em Acyclic Cutsets},'' In: 7th C5 Graph Theory Workshop, Kurort Rathen, 12.--16.05.2003.\\ \texttt{http:/\!/www.mathe.tu-freiberg.de/math/inst/theomath/WorkshopRathen.html} \bibitem{KleFig} S. Klein, C.M.H. de Figueiredo, The NP-completeness of multi-partite cutset testing, Congressus Numerantium 119 (1996) 217-222. \bibitem{LMM} V.B. Le, R. Mosca, H. M\"uller, On stable cutsets in claw-free graphs and planar graphs, J. Discrete Algorithms 6 (2008) 256-276. \bibitem{LeRand} V.B. Le, B. Randerath, On stable cutsets in line graphs, Theoret. Comput. Sci. 301 (2003) 463-475. \bibitem{C5W2003} ``Selected open problems,'' In: 7th C5 Graph Theory Workshop, Kurort Rathen, 12.--16.05.2003.\\ \texttt{http:/\!/www.mathe.tu-freiberg.de/math/inst/theomath/WorkshopRathen.html} %\bibitem{Tarjan} R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. \bibitem{Tucker} A. Tucker, Coloring graphs with stable cutsets, J. Combin. Theory (B) 34 (1983) 258-267. %\bibitem{White} S.H. Whitesides, An algorithm for finding clique cut-sets, Inf. Process. Lett. 12 (1981) 31-32. \end{thebibliography} \end{document}