\mychapter{$K_{4}$-Saturated Graphs}
\label{chapter:K_4}

%07/13/10



As we have seen in the inroduction, saturation numbers are not a monotone property.  So it would be nice to know the sizes of all $H$-saturated graph for any graph $H$.  In this chapter, we find the sizes of all $K_4$-saturated graphs.  We know that any $K_{4}$-saturated graph has at least $2n-3$ edges and at most $\lfloor n^{2}/3 \rfloor$ edges and these bounds are sharp.  The emphasis of this chapter is to prove that there is an $(n, m) \mbox{ } K_4$-saturated graph $G$ if and only if $G$ is a complete tripartite graph or $3n-8 \leq m \leq \frac{n^2 - n + 4}{3}$.   We show the lower bound of the interval using the minimum degree of the graph.  We apply a result by Hanson and Toft \cite{ht91} to show the upper bound of our result.  We also found the exact structure of $K_4$-saturated graphs of connectivity $2$ and $3$.  We also proved that $K_4$-saturated graphs have diameter $2$ and are also $2$-connected.







\section{Results on $K_{4}$-saturated Graphs}
\label{sec:Resultson$K_{4}$-saturatedGraphs}

The distance between two vertices $u$ and $v$, denoted by $d(u,v)$, is the length of the shortest path connecting 
them.  The diameter, denoted by $diam(G)$, of a graph $G$ is the maximal distance between any two vertices on 
the graph.  We have the following relationship between a $K_4$-saturated graph $G$ and its diameter.


\begin{proposition} \label{prop1}
Let $G$ be a $K_{4}$-saturated graph.  Then $diam(G) = 2$.
\end{proposition}
\proof
Let $G$ be a $K_{4}$-saturated graph.  Suppose $diam(G) \neq 2$, that is, suppose there exists vertices
$u,v \in V(G)$ such that $d(u,v) = 3$.  Say $u, x, y, v$ is a $u-v$ distance $3$ path.
Then the addition of the edge $uv$ must produce a $K_{4}$.  So there must exist vertices
$a, b$ such that the induced subgraph $\langle u, a, b, v \rangle \cong K_{4}$.
But now we have $d(u,v) = 2$, as $u, a, v$ is such a path, a contradiction.
\qed


A vertex $u$ is said to be {\it connected} to a vertex $v$ in a graph $G$ if there exists a $u-v$ path in $G$.  A graph $G$ is {\it connected} if every two of its vertices are connected.  A graph that is not connected is {\it disconnected}.  A {\it vertex-cut} in a graph $G$ is a set $U$ of vertices of $G$ such that $G - U$ is disconnected.  The {\it vertex connectivity} or simply the {\it connectivity} $\kappa(G)$ of a graph $G$ is the minimum cardinality of a vertex-cut of $G$ if $G$ is not complete, and $\kappa(G) = n-1$ if $G = K_n$ for some positive integer $n$.  A graph $G$ is said to be $k$-{\it connected}, $k \geq 1$, if $\kappa(G) \geq k$.  

%Furthermore, if $G$ is $K_4$-saturated graph, then $G$ is $2$-connected.

\begin{proposition} \label{prop2}
Let $G$ be a $K_{4}$-saturated graph.  Then $G$ is $2$-connected.
\end{proposition}
\proof
Let $G$ be a $K_{4}$-saturated graph.  Suppose $G$ is not $2$-connected.  Let $u$ be the cut
vertex and let $A$ and $B$ be components of $G-u$ with $x \in V(A)$ and $y \in V(B)$ (see Figure $2.1$).


\begin{figure}[ht!]
\begin{center}
\epsfxsize 1.5in \epsfbox{figure1.eps}
\caption{$G$}
\end{center}
\end{figure}


Now the addition of the edge $xy$ creates a $K_{4}$.  So there exists a vertex $w \neq u$ such that
$wx \in E(G)$ and $wy \in E(G)$.  Then $x$ and $y$ are connected in $G - u$, a contradiction.
\qed


Next we show that there is only one $K_4$-saturated graph with minimum degree two.

\begin{theorem}\label{thm1}
Let $G$ be a $K_{4}$-saturated graph.  Then either $G \cong K_{1,1,n-2}$ or $\delta(G) \geq 3$.
\end{theorem}
\proof
Let $G$ be a $K_{4}$-saturated graph.  Let $v \in V(G)$ such that $N(v) = \{x, y \}$.  Then for
all the vertices $z \in V(G) - \{x, y, v\}$, the addition of the edge $vz$ must produce a $K_{4}$
with vertex set $\{v, x, y, z \}$.  Thus, $xy, xz, yz \in E(G)$.  Since $z$ was chosen arbitrarily,
in fact, all vertices in $V(G) - \{x, y, v\}$ are adjacent to both $x$ and $y$.  So $K_{1,1,n-2} \subseteq G$.
But $K_{1,1,n-2}$ is $K_{4}$-saturated, so $G \cong K_{1,1,n-2}$.
\qed


Now, we know that we can obtain a $K_4$-saturated graph from a $K_3$-saturated graph joined with an independent set of vertices.  We show that no other sizes of $K_4$-satuarted graphs exists in the following three lemmas.  Before we prove these lemmas, we make the following two observations about $K_{4}$-saturated graphs $G$:


\begin{enumerate}
\item  The neighborhood of every vertex contains an edge.

\item  For all vertices $u,v \in V(G)$, $uv \notin E(G)$ if and only if
  there exists an edge in the common neighborhood of $u$ and $v$.
\end{enumerate}



\begin{lemma}\label{lem1}
If $G$ is a $K_{4}$-saturated graph of order $n$ and $\delta(G) = 3$, then $|E(G)| \geq 3n-8$.
\end{lemma}
\proof
Let $v \in V(G)$ such that $N(v) = \{x, y, z\}$.  Let $W = V(G) - \{v, x, y, z \}$.
Note that the induced graph $\langle x, y, z\rangle$ is not isomorphic to $K_{3}$.

If $\langle x, y, z\rangle$ contains precisely one edge, say $xy$, then by observation $2$, every vertex $w \in W$ must
also be adjacent to $x, y$ and  $W$ is therefore independent.
But this would force $N(z)$ to be independent, contradicting observation 1.

If $\langle x, y, z\rangle$ contains precisely two edges, say $xy, yz$, then by observation 2, $W$
can be partitioned into three sets $W_{xy}, W_{yz}, W_{xyz}$, where $W_{xy}= \{w \in W | N(w) \cap
\{x, y, z \} = \{x, y \} \}$ with $W_{yz}$ and $W_{xyz}$ defined similarly (note that $W_{xz} = \emptyset$).  Each of these
are independent sets of vertices.  Furthermore, if $w \in W_{xyz}$, then it has no adjacencies
to $W_{xy}$ or $W_{yz}$.  Let $w_{1} \in W_{xy}$ and $w_{2} \in W_{yz}$.  Then
$N(w_{1}) \cap N(w_{2}) = \{y \}$.  Thus, by observation $2$, they must be adjacent.  Hence, $W_{xy}$ and $W_{yz}$
must induce a complete bipartite graph.  Let $|W_{xyz}| = h, |W_{yz}| = l, |W_{xy}| = n-h-l-4$.  Then,


\begin{eqnarray*}
|E(G)| & = & 5 + 2l + 2(n-h-l-4) + l(n-h-l-4) + 3h \\ & = & (2+l)n + (1-l)h - l^{2} - 4l-3.
\end{eqnarray*}


Let $f(l) = (2+l)n + (1-l)h - l^{2} - 4l-3$.  Note if $l = 0$, then we are done by our previous argument.
Now $f(1) = 3n-8$.  Furthermore, $f$ is maximized at $l = \frac{n-h-4}{2}$ and is increasing between
$l=1$ and $l=\frac{n-h-4}{2}$.  Note this is all of the relevant interval for $l$, since we can
assume, without loss of generality, $|W_{yz}| \leq |W_{xy}|$.
\qed



\begin{lemma}\label{lem2}
If $G$ is a $K_{4}$-saturated graph of order $n$ and $\delta(G) = 4$, then $|E(G)| \geq 3n-8$.
\end{lemma}
\proof
Let $v \in V(G)$ such that $d(v) =4$ and $|V(G)| = n$.  Let $N(v) = A = \{ a_{1}, a_{2}, a_{3}, a_{4} \}$.
Let $W = V(G) - A - \{ v \}$. Then there must exist an edge $a_{i}a_{j}$ for some $i,j, 1\leq i, j \leq 4$ as
for any vertex $w \in W$, addition of the edge $vw$ must create a $K_{4}$.


If $\langle A \rangle$ contains precisely one edge, say $a_{1}a_{2}$, then every vertex $w \in W$ must
also be adjacent to $a_{1}, a_{2}$ by observation 2 above and  $W$ is therefore independent.
But this would force $N(a_{3})$ and $N(a_{4})$ to be independent, contradicting observation 1.  So
$\langle A \rangle$ must contain at least two edges. So now assume that there are precisely two edges
among the vertices of $A$.  Then we have two possibilities as shown in the Figure $2.2$.


\begin{figure}[ht!]
\begin{center}
\epsfxsize 3in \epsfbox{figure3.eps}
\caption{$G$}
\end{center}
\end{figure}


Pick the vertices $a_{i}$ and $a_{j}$ in different components of $\langle N(v) \rangle$.  The addition of the edge
$a_{i}a_{j}$must produce a $K_{4}$ with an edge in $W$, say $w_{1}w_{2}$.  But each vertex $w_{i}$, for $i =
1,2$, must be adjacent to an edge in $A$, or else the addition of the edge $vw_{i}$ would not
produce a $K_{4}$.  Hence, $w_{1}$ and $w_{2}$ are adjacent to at least three vertices
of $A$.

The count below comes from counting the degree sum in the following parts: $(1)$ the degree sum in
$v \cup A$, $(2)$ the degree sum from $A$ to $W$, $(3)$ the degree sum of vertices in $W$.  In the
last instance we use the assumption that $\delta(G) = 4$.

\begin{eqnarray*}
\sum_{x \in V(G)} d(x) & \geq & (4+4+4)+(2(n-5)+2)+(4(n-5)) \\ & = & 6n-16.
\end{eqnarray*}


Observe that if there are three edges among the vertices of $A$, we also obtain the same count.
Hence, $|E(G)| \geq 3n-8$.
\qed




\begin{lemma}\label{lem3}
If $G$ is a $K_{4}$-saturated graph and $\delta(G) = 5$, then $|E(G)| \geq 3n-8$.
\end{lemma}
\proof
Note that $|E(G)| \geq \frac{5n}{2}$ and $\frac{5n}{2} \geq 3n-8$ for $n \leq 16$.

%If $5 \leq n \leq 7$, the result is trivial.  For $n= 8$, $|E(G)| \geq \frac{5*8}{2} = 20$
%and $3n-8 = 3*8 - 8 = 16$.  Now consider $n \geq 9$.

Let $v \in V(G)$ with $d(v) =5$ and $|V(G)| = n \geq 17$.
Let $N(v) = A = \{ a_{1}, a_{2}, a_{3}, a_{4}, a_{5} \}$.
Let $W = V(G) - A - \{ v \}$.  We know there must exist an edge $a_{i}a_{j}$ for some
$i,j$.  In fact, as in Lemma~\ref{lem2}, there must exist at least two
edges.  Furthermore, for any vertex $w \in W$, $wa_{i}$ and $wa_{j}$ must exist for
some $i,j, 1 \leq i, j \leq 5$.  Also, two of the vertices in $W$ must be adjacent
to at least $3$ vertices in $A$, as shown in Lemma~\ref{lem2}.  Since $\delta(G) = 5$ and counting
as we did in the previous lemma, we have


\begin{eqnarray*}
\sum_{x \in V(G)} d(x) & \geq & (5+5+4)+(2(n-6)+2)+(5(n-6)) \\ & = & 7n-26
\end{eqnarray*}


So, $|E(G)| \geq \frac{7n-26}{2} \geq 3n-8$ for $n \geq 10$.
%Hence, $|E(G)| \geq 3n + \frac{n}{2} - \frac{25}{2}$ for $n \geq 9$.  Hence, $|E(G)| \geq 3n-8$.
\qed




\begin{theorem}\label{thm2}
Every $2$-connected $K_{4}$-saturated graph of order $n$ with $\delta(G) \geq 3$ has at least $3n-8$ edges.
\end{theorem}
\proof
From Lemmas~\ref{lem1} - ~\ref{lem3}, the result holds for graphs $G$ with $3 \leq \delta(G) \leq 5$.
For graphs $G$ with $\delta(G) \geq 6$, $|E(G)| \geq \frac{6n}{2} = 3n$.
\qed



\bigskip



Recall that the {\it connectivity} $\kappa(G)$ of a graph $G$ is the minimum number of vertices whose removal results in a disconnected or trivial graph.  In the following two theorems, we classify all $K_{4}$-saturated graphs $G$ with $\kappa(G)=2$ or $\kappa(G)=3$.


\begin{theorem}\label{thm3}
If $G$ is a $K_{4}$-saturated graph of order $n$ with $\kappa(G) = 2$, then $G \cong K_{1,1,n-2}$.
\end{theorem}
\proof
Let $G$ be a $K_{4}$-saturated with $\kappa(G)=2$.  Let $K$ be a minimal cut set of $G$ and let
$C_{1}, C_{2}$ be distinct components of $G - K$.  Let $x_{i} \in V(C_{i})$ for $i=1, 2$.  Then the addition
of the edge $x_{1}x_{2}$ produces a $K_{4}$.  So if $u,v \in K$, then $\langle x_{1}, x_{2}, u, v \rangle \cong K_{4}$.
As $x_{1}$ ($x_{2}$) was an arbitrary vertex of $C_{1}$ ($C_{2}$), each vertex in $C_{1}$ ($C_{2}$) is also
adjacent to $u$ and $v$.  So $G - K$ is an independent set and the result is shown.
\qed



Now we will classify all $K_{4}$-saturated graphs with $\kappa(G) = 3$.  But first, we define the graph $W(a,b,c,d,e)$ to be a wheel on $5$ sets totalling $n$ vertices such that $a+b+c+d+e = n-1$ and each of the $5$ sets of the wheel are independent sets of sizes $a, b, c, d, e$, respectively, and two consecutive independent sets on the wheel form a complete bipartite subgraph.  

\smallskip 


\begin{theorem}\label{thm4}
If $G$ is a $K_{4}$-saturated graph of order $n$ with $\kappa(G) = 3$, then
$G \cong K_{1,2,n-3}$ or $G \cong W(1,t,1,r,s)$.

\begin{figure}[ht!]
\begin{center}
\epsfxsize 1.5in \epsfbox{figure6.eps}
\caption{$W(1,t,1,r,s)$\label{something}}
\end{center}
\end{figure}

\end{theorem}
\proof
Let $K$ be a minimal cut set of $G$, say $\{ v_{1}, v_{2}, v_{3} \}$.  Let $C_{1}, C_{2}$ be distinct
components of $G - K$.  Let $x_{i} \in V(C_{i})$ for $i=1, 2$.  Then addition of the edge
$x_{1}x_{2}$ produces a $K_{4}$.  Without loss of generality, suppose
$\langle x_{1}, x_{2}, v_{1}, v_{2} \rangle \cong K_{4}$.  If all the components of $G - K$
are trivial, then all are adjacent to all three vertices of $K$ by the connectivity
assumption.  Now one of (but not both) $v_{1}$ or $v_{2}$ is adjacent to $v_{3}$
(say $v_{2}$) or else inserting the edge $v_{2}v_{3}$ would not produce a $K_{4}$.  But now $G$ is $K_{1,2,n-3}$.

We now assume $C_{1}$ is nontrivial.  Let $x_{3}$ be a neighbor of $x_{1}$ in $C_{1}$.  Inserting the
edge $x_{2}x_{3}$, we know (without loss of generality) $\langle x_{2}, x_{3}, v_{2}, v_{3} \rangle \cong K_{4}$, since $x_{3}$ cannot be
adjacent to both $v_{1}$ and $v_{2}$.  If there exists a vertex $x_{4} \in V(C_{2})$ such that
$x_{2}x_{4} \in E(G)$, then by a similar argument $x_{4}v_{1}, x_{4}v_{2},x_{4}v_{3} \in E(G)$.
Hence, $\langle x_{2}, x_{4}, v_{1}, v_{2} \rangle \cong K_{4}$.  Hence, $V(C_{2}) = \{ x_{2} \}$.  In fact
$G - \{ K \cup C_{1} \}$ is an independent set.  For every
$w \in V(C_{1}), N(w) \cap K = \{ v_{1}, v_{2} \}$ or $N(w) \cap K = \{ v_{2}, v_{3} \}$
since $w$ must be adjacent to an edge in $K$ but cannot be in a $K_{4}$.  Now partition $C_{1}$ into two
classes $A$ and $B$, where vertices of $A$ are adjacent to $v_{1}$ and $v_{2}$, while vertices of $B$
are adjacent to $v_{2}$ and $v_{3}$.  Clearly, $A$ is an independent set.  Similarly, $B$ is an
independent set.

We claim $\langle A \cup B \rangle$ is a complete bipartite graph.  Let $a \in A, b \in B$
such that $ab \notin E(G)$.  Then addition of the edge $ab$ must produce a $K_{4}$.
Since $A$ and $B$ are independent sets, the edge they have in common has to be in $K$,
a contradiction.  Hence, $\langle A \cup B \rangle$ is complete bipartite.  Thus, if $|A|=s$
and $|B| = r$, using $v_2$ as the center of the wheel, we have $G \cong W(1, t, 1, r, s)$,
where $3+t+r+s=n$.
\qed







\section{Hanson and Toft Result}
\label{sec:HansonandToftResult}



In this section, we give a construction due to Hanson and Toft \cite{ht91} that produces the maximum size of a $K_t$-saturated graph $G$ on $n \geq t+2$ vertices with $\chi(G) \geq t$.  The graphs in the family
$\mathcal{T}_n^t$ are on $n$ vertices consisting of a complete $(t-1)$-partite graph on $n-2$
vertices, with classes of independent points $C_1, C_2, . . . , C_{t-1}$, together with two adjacent
vertices $x$ and $y$ and where each vertex of $C_1$ is joined to precisely one of $x$ or $y$, $x$
and $y$ are each  adjacent to at least one vertex of $C_1$, no vertex of $C_2$ is adjacent to either $x$
or $y$ and all vertices of $C_i$, $i > 2$ are adjacent to both $x$ and $y$.  For $t \geq 3$, define
$T'_{t-1,n}$ to be graphs in $\mathcal{T}_n^t$ for which $|C_1|+1, |C_2|+2, |C_3|, . . . ,
|C_{t-1}|$ are equal or as equal as possible.  For $n \geq 3t-4$ we can describe $T'_{t-1, n}$ as
follows: let $n+1 = k(t-1)+r$, $0 \leq r < t-1$ and let $G$ denote a member of $\mathcal{T}_{n_0}^t$
on $n_0 = n-r$ vertices and $e_0 = e(T_{t-1,n-r}) - (k-2)$ edges where the classes $C_i$ satisfy
$|C_1| = k-1, |C_2| = k-2$ and $|C_i| = k$, $i> 2$ ($G$ is unique up to adjacencies of $x$ and $y$
to class $C_1$).  Define $T'_{t-1,n}$ to be a graph $G$ with one vertex added to precisely $r$
of the classes $C_1, . . . , C_{t-1}$.  Note that the graphs $T'_{t-1,n}$ are maximal, with respect
to the number of edges, in the family $\mathcal{T}_n^t$.  Then Hanson and Toft \cite{ht91}
showed the following result.


\begin{theorem}\label{thmHT}
Let $G$ be a $K_{t}$-saturated graph on $n \geq t+2 \geq 5$ vertices with $\chi(G) \geq t$,
then $G$ is a $T'_{t-1,n}$ graph.
\end{theorem}



\begin{theorem}\label{thm5}
If $G$ is a $K_{4}$-saturated graph of order $n$ and $G$ is not complete
tripartite, then $|E(G)| \leq \frac{n^{2}-n+4}{3}$.
\end{theorem}
\proof
Let $G$ be a $K_4$-saturated graph of order $n$.  Suppose $G$ is not a complete tripartite graph.
Since $G$ is not tripartite, $\chi(G) \geq 4 = t$.  Hence, by Theorem~\ref{thmHT},
$|E(G)| \leq |E(T'_{3,n})|$.  For $n+1 = 3k + r$, a straight forward computation shows,
$|E(T'_{3,n})| \leq \frac{n^2-n+4}{3}$.  In fact, when $r = 0$, $|E(T'_{3,n})| = \frac{n^2-n+4}{3}$.
Hence, $|E(G)| \leq \frac{n^2-n+4}{3}$.
\qed









\section{The Edge Spectrum of $K_4$-Saturated \\ Graphs}
\label{sec:TheEdgeSpectrumof$K_4$-SaturatedGraphs}


We now show a $K_4$ analogue of Theorem ~\ref{barefoot2}

\begin{theorem}\label{main}
Let $n \geq 5$ and $m$ be nonnegative integers.  There is an $(n, m)$
$K_{4}$-saturated graph $G$ if and only if $3n-8 \leq m \leq \frac{n^{2}-n+4}{3}$
or $m = rs+st+rt$ for some positive integers $r, s, t$ where $n = r + s+ t$.
\end{theorem}
\proof
Let $n \geq 5$ and $m$ be nonnegative integers.  Let $G$ be  an $(n, m)$
$K_{4}$-saturated graph.  If $G$ is a tripartite graph, then $G$ must be a
complete tripartite graph, otherwise an edge may be added without creating
a $K_{4}$.  Now if $G \cong K_{1,1,n-2}$, then $m = 2n-3$ and clearly $r = s = 1$ while $t = n-2$, otherwise
$m = rs+st+rt$ for some positive integers $r, s, t$ such that $n = r+s+t$.

Now let $G$ be a nontripartite graph.  Then from Theorem~\ref{thm2}, Theorem~\ref{thm4},
and Theorem~\ref{thm5}, we have that $3n-8 \leq m \leq \frac{n^{2}-n+4}{3}$.

It is sufficient to construct an $(n, m)$ $K_{4}$-saturated graph for each value
of $m$.  If $m = 2n-3$, then $G \cong K_{1,1,n-2}$.  If $m =rs+st+rt$ for some
positive integers $r,s, t$ where $n = r + s+ t$, then $G \cong K_{r,s,t}$ with $m$ edges.

Now let  $3n-8 \leq m \leq \frac{n^{2}-n+4}{3}$.  From Theorem 3.2 (from Chapter 1, Introduction), there exist a $K_3$-saturated graph $H$ of order $n-q$ with $2(n-q) -5 \leq |E(H)| \leq \lfloor \frac{(n-q-1)^{2}}{4} \rfloor +1$, for $1 \leq q \leq n-5$.  Take $G \cong H + \overline{K_{q}}$.  Then $G$ is clearly a $K_4$-saturated graph.  Now $2(n-q) - 5 + (n-q)q \leq |E(G)| \leq \lfloor \frac{(n-q-1)^{2}}{4} \rfloor + 1 + (n-q)q$.  For $q=1$, $3n-8 \leq |E(G)| \leq \lfloor \frac{n^2+4}{4} \rfloor$; for $q=2$, $4n-13 \leq |E(G)| \leq \lfloor \frac{n^2 + 2n - 3}{4} \rfloor$; . . . ; for $q=n-5$, $5n - 20 \leq |E(G)| \leq 10n - 20$.  It can be easily seen that these intervals overlap.  Furthermore, we obtain the lower bound when $q=1$, $3n-8$.  Now let $f(q)= \lfloor \frac{(n-q-1)^{2}}{4} \rfloor + 1 + (n-q)q$.  Then $f(q)$ is
maximum when $ q = \frac{n+1}{3}$ and $f(\frac{n+1}{3}) = \frac{n^{2}-n+4}{3}$.  
\qed


In the above Theorem, the lower and upper bounds are achieved.  For example, for the
following graphs $G_{1}$ (Figure $4$) and $G_{2}$ (Figure $5$), lower and upper bounds,
respectively, are achieved.

\smallskip 


\begin{figure}[ht!]
\begin{center}
\epsfxsize 2.5in \epsfbox{figure8.eps}
\caption{$G_{1}$}
\end{center}
\end{figure}


\begin{figure}[ht!]
\begin{center}
\epsfxsize 2.5in \epsfbox{figure9.eps}
\caption{$G_{2}$}
\end{center}
\end{figure}


