On disjoint matchings in cubic graphs: maximum $3$-edge-colorable subgraphs
Vahan V. Mkrtchyan\address[MCSD]{Department of Informatics and Applied Mathematics,
We show that any $2-$factor of a cubic graph can be extended to a maximum $3-$edge-colorable subgraph. We also show that the sum of sizes of maximum $2-$ and $3-$edge-colorable subgraphs of a cubic graph is at least twice of its number of vertices.
ArticleFinal.tex
%%%%%%%%%% espcrc1.tex %%%%%%%%%%
%
% $Id: espcrc1.tex,v 1.2 2004/02/24 11:22:11 spepping Exp $
%
\documentclass[fleqn,12pt,twoside]{article}

%\usepackage{espcrc1}

%Use the option 'headings' if you want running headings
\usepackage[headings]{espcrc1}
%\texttt{espcrc}
% identification
\readRCS $Id: espcrc1.tex,v 1.2 2004/02/24 11:22:11 spepping Exp $
\ProvidesFile{espcrc1.tex}[\filedate \space v\fileversion
     \space Elsevier 1-column CRC Author Instructions]

% change this to the following line for use with LaTeX2.09
% \documentstyle[12pt,twoside,fleqn,espcrc1]{article}

% if you want to include PostScript figures
\usepackage{graphicx}
% if you have landscape tables
\usepackage[figuresright]{rotating}

% put your own definitions here:
%   \newcommand{\cZ}{\cal{Z}}
%   \newtheorem{def}{Definition}[section]
%   ...
\newtheorem{theorem}{Theorem}
\newtheorem{algorithm}{Algorithm}
\newtheorem{axiom}{Axiom}
\newtheorem{case}{Case}
\newtheorem{claim}{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}{Problem}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}

\newenvironment{dedication}[1][]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newenvironment{proof}[1][Proof.]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newenvironment{acknowledgement}[1][Acknowledgement]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\ttbs}{\char'134}
\newcommand{\AmS}{{\protect\the\textfont2
  A\kern-.1667em\lower.5ex\hbox{M}\kern-.125emS}}

% add words to TeX's hyphenation exception list
\hyphenation{author another created financial paper re-commend-ed
Post-Script}

%\usepackage{theorem}
% set the starting page if not 1
% \setcounter{page}{17}
\usepackage{amsmath}
\usepackage{amsfonts}
% declarations for front matter
\title{On disjoint matchings in cubic graphs: maximum $3$-edge-colorable subgraphs}

\author{Vahan V. Mkrtchyan\address[MCSD]{Department of Informatics and Applied Mathematics,\\
Yerevan State University, Yerevan, 0025, Armenia}%
\address{Institute for Informatics and Automation Problems,\\
National Academy of Sciences of Republic of Armenia, 0014, Armenia}
\thanks{email: vahanmkrtchyan2002@\{ysu.am, ipia.sci.am,
yahoo.com\}},
        Samvel S. Petrosyan\addressmark[MCSD]\thanks{email: samvelpetrosyan2008@yahoo.com},
                and
        Gagik N. Vardanyan\addressmark[MCSD]\thanks{email: vgagik@gmail.com}}

% If you use the option headings,
% the title is also used as the running title,
% and the authors are also used as the running authors.
% You can change that by using \runtitle and \runauthor.

\runtitle{On disjoint matchings in cubic graphs: maximum $3$-edge-colorable subgraphs}
\runauthor{Vahan Mkrtchyan, Samvel Petrosyan, Gagik
Vardanyan}

\begin{document}

% typeset front matter
\maketitle

\begin{abstract}
We show that any $2-$factor of a cubic graph can be extended to a
maximum $3-$edge-colorable subgraph. We also show that the sum of sizes of
maximum $2-$ and $3-$edge-colorable subgraphs of a cubic graph is at
least twice of its number of vertices.
\end{abstract}


\section{Introduction}

We consider finite undirected graphs that do not contain loops. For a graph $G$ and a positive integer $k$ define

\begin{center}
$B_{k}(G)\equiv \{(H_{1},...,H_{k}):H_{1},...,H_{k}$ are pairwise
edge-disjoint matchings of $G\}$,
\end{center}

and let

\begin{center}
$\nu _{k}(G)\equiv \max \{\left\vert H_{1}\right\vert
+...+\left\vert H_{k}\right\vert :(H_{1},...,H_{k})\in B_{k}(G)\}$.
\end{center}

A subgraph $H$ of $G$ is called maximum $k$-edge-colorable, if it is $k$-edge-colorable
and contains exactly $\nu _{k}(G)$ edges.

Terms and concepts that we do not define can be found in \cite{Lov,West}.

\section{The main results}

The first theorem allows us to "embed" maximum $3-$edge-colorable
subgraphs of a cubic graphs into minimum $4-$edge-colorings. Having
done this, we can apply the results of \cite{SteffenClassification,Steffen} for the investigation of our
problems.

\begin{theorem}\label{ComplementMatching}Let $H$ be a maximum $3-$edge-colorable
subgraph of a cubic graph $G$. Then $E(G)\backslash E(H)$ is a
matching.
\end{theorem}

\begin{proof} 

First of all let us show that the graph $G\backslash
E(H)$ contains no path of length three. On the opposite assumption,
consider a path $u_0,u_1,u_2,u_3$ of the graph $G\backslash E(H)$,
and let us assume that $H$ is properly colored with colors
$\{1,2,3\}$. Define the sets $C(u_0),C(u_1),C(u_2)$ as the colors of
the edges incident to the vertices $u_0,u_1,u_2$, respectively.

Note that
\begin{equation*}
|C(u_0)|\leq2.
\end{equation*}

If $|C(u_0)|<2$, then there is $\alpha \in \{1,2,3\}$ with $\alpha
\notin C(u_0)\cup C(u_1)$. Now, if we color the edge $(u_0,u_1)$
with color $\alpha$, then we would get a proper $3-$edge-coloring of
the subgraph $H\cup \{(u_0,u_1)\}$, contradicting the maximality of
$H$. Thus:
\begin{equation*}
|C(u_0)|=2.
\end{equation*}
Now, let us show that
\begin{equation}
|C(u_1)|=1\textrm{ and }C(u_0)\cup
C(u_1)=\{1,2,3\}.\label{unionColors}
\end{equation}
Assume the contrary, that is $C(u_1)\subseteq C(u_0)$. There is
$\alpha \in \{1,2,3\}$ with $\alpha \notin C(u_0)$. Now, if we color
the edge $(u_0,u_1)$ with color $\alpha$, then we would get a proper
$3-$edge-coloring of the subgraph $H\cup \{(u_0,u_1)\}$,
contradicting the maximality of $H$.

Thus, (\ref{unionColors}) must be true. Since $|C(u_1)\cup
C(u_2)|\leq2$, then there is $\alpha \in \{1,2,3\}$ with $\alpha
\notin C(u_1)\cup C(u_2)$. Now, if we color the edge $(u_1,u_2)$
with color $\alpha$, then we would get a proper $3-$edge-coloring of
the subgraph $H\cup \{(u_1,u_2)\}$, contradicting the maximality of
$H$.

Thus, the graph $G\backslash E(H)$ contains no path of length three.
To complete the proof of the theorem, we need to verify the absence
of adjacent edges in $G\backslash E(H)$.

Suppose that $(u_0,u_1),(u_1,u_2)\in E(G)\backslash E(H)$. Again,
let $C(u_0),C(u_1),C(u_2)$ denote the colors of the edges incident
to the vertices $u_0,u_1,u_2$, respectively. We need to consider two
cases:

Case 1: $u_0=u_2$, that is, $(u_0,u_1)$ is a multiple edge. Note
that $|C(u_0)|\leq1,|C(u_1)|\leq1$, thus there is $\alpha \in
\{1,2,3\}$ with $\alpha \notin C(u_0)\cup C(u_1)$. Now, if we color
one of edges connecting $u_0$ and $u_1$ with color $\alpha$, then we
would get a proper $3-$edge-coloring of the subgraph $H\cup
\{(u_0,u_1)\}$, contradicting the maximality of $H$.

Case 2: $u_0\neq u_2$. Note that
$|C(u_0)|\leq2,|C(u_1)|\leq1,|C(u_2)|\leq2$. Like in the proof of
(\ref{unionColors}), one can easily show that
\begin{gather*}
C(u_0)\cup C(u_1)=\{1,2,3\}, \textrm{ and }C(u_1)\cup
C(u_2)=\{1,2,3\},
\end{gather*}
thus $C(u_0)=C(u_2)$. Suppose that $C(u_0)=C(u_2)=\{\alpha, \beta\}$
and $C(u_1)=\{\gamma\}$. Consider the maximal $\alpha - \gamma$
alternating paths $P_0,P_1,P_2$, starting from vertices
$u_0,u_1,u_2$, respectively. Note that there is $i\in \{0,2\}$ such
that $u_1\notin V(P_i)$. Now, shift the colors on the path $P_i$ to
obtain a new coloring of the maximum $3-$edge-colorable subgraph
$H$, where the color $\alpha$ is absent in both of vertices $u_i$
and $u_1$. Now, if we color the edge $(u_1,u_i)$ with color
$\alpha$, then we would get a proper $3-$edge-coloring of the
subgraph $H\cup \{(u_1,u_i)\}$, contradicting the maximality of $H$.
The proof of the theorem \ref{ComplementMatching} is completed.
\end{proof}

It is not always possible to extend a $1$-factor into a maximum $2$-edge-colorable
subgraph of a cubic graph. Nevertheless, the following is true:

\begin{theorem}\label{1factorExtension}Any $1-$factor of a cubic graph $G$ can be extended
to a maximum $3-$edge-colorable subgraph of $G$.
\end{theorem}
\begin{proof}For a $1-$factor $F$ of $G$, choose a maximum $3-$edge-colorable
subgraph $H$ of $G$ with
\begin{equation*}
|E(F)\cap E(H)|\rightarrow max.
\end{equation*}
Let us show that $E(F)\subseteq E(H)$. On the opposite assumption,
consider an edge $e=(u,v)\in E(F)\backslash E(H)$ and let us assume
that $H$ is properly colored with colors $\{1,2,3\}$. Due to theorem
\ref{ComplementMatching}, the edges adjacent to $e$ are belong to
$H$. Let $C(u)$ and $C(v)$ denote the colors of edges that are
incident to $u$ and $v$, respectively. Note that the maximality of
$H$ implies that
\begin{equation*}
|C(u)\cap C(v)|=1\textrm{ and }C(u)\cup C(v)=\{1,2,3\}.
\end{equation*}
Choose $\alpha \in C(u)\backslash C(v)$. Consider the subgraph
$H'=(H\backslash \{e'\})\cup \{e\}$, where $e'$ is the edge that is
incident to $u$ and is colored by $\alpha$. Note that $H'$ is a
maximum $3-$edge-colorable subgraph of $G$ with
\begin{equation*}
|E(F)\cap E(H)|<|E(F)\cap E(H')|.
\end{equation*}contradicting the choice of $H$. The proof of the
theorem \ref{1factorExtension} is completed.
\end{proof}

Next, we prove a result which claims that the uncolored edges with
respect to a maximum $3-$edge-colorable subgraph of $G$ always can
be "left" in a given $1-$factor, or, equivalently, any $2-$factor of
a cubic graph $G$ can also be extended to a maximum $3-$edge-colorable
subgraph of $G$.

\begin{theorem}\label{2factorExtension}Let $F$ be any $1-$factor of a cubic graph $G$, and let $\bar{F}$
be the complementary $2-$factor of $F$. Then there is a maximum
$3-$edge-colorable subgraph $H$ of $G$, such that:
\begin{enumerate}
\item[(a)] $E(H)\cup E(F)=E(G);$

\item[(b)] $E(\bar{F})\subseteq E(H).$

\end{enumerate}
\end{theorem}
\begin{proof} Note that (b) follows from (a), thus we will stop only
on the proof of (a).

For a given $1-$factor $F$ of a cubic graph $G$, consider a maximum
$3-$edge-colorable subgraph $H$ of $G$ with
\begin{equation*}
|E(F)\cap E(H)|\rightarrow min.
\end{equation*}
Let us show that $E(H)\cup E(F)=E(G)$. We only need to verify that
$E(F)\cup E(H)\supseteq E(G)$. Assume that there is $e\in E(G)$ such
that $e$ belongs to neither of $F$ and $H$, and let us assume that
$H$ is properly colored with colors $\{1,2,3\}$.

Consider the edges adjacent to $e$. Due to theorem
\ref{ComplementMatching}, these edges belong to $H$. If $C(u)$ and
$C(v)$ denote the colors of edges that are incident to $u$ and $v$,
respectively, then the maximality of $H$ implies that
\begin{equation*}
|C(u)\cap C(v)|=1\textrm{ and }C(u)\cup C(v)=\{1,2,3\}.
\end{equation*}
Suppose that
\begin{equation*}
\{\alpha\}=C(u)\cap C(v), C(u)=\{\alpha,\beta \} \textrm{ and }
C(v)=\{\alpha,\gamma\}.
\end{equation*}
Due to \cite{SteffenClassification,Steffen}, there is an odd cycle $C_e$ containing the edge $e$, whose all other edges are
colored $\beta$ and $\gamma$, alternatively, while the edges that
are incident to a vertex of $C_e$ and do not lie on $C_e$, are
colored by $\alpha$. We need to consider two cases:

Case 1:$E(C_e)\cap E(F)\neq \emptyset$.

Let $f\in E(C_e)\cap E(F)$. Consider a proper partial
$3-$edge-coloring of the graph $G$ obtained from the coloring of $H$
as follows: $f$ is left uncolored, the edges of the even path
$C_e-f$ are colored $\beta$ and $\gamma$, alternatively, the colors
of the rest of edges are left unchanged. Note that the new partial
$3-$edge-coloring corresponds to a maximum $3-$edge-colorable
subgraph $H'$ of $G$ with
\begin{equation*}
|E(F)\cap E(H')|<|E(F)\cap E(H)|
\end{equation*}contradicting the choice of $H$.

Case 2:$E(C_e)\cap E(F)=\emptyset$.

Note that in this case,
\begin{enumerate}
\item[(I)] the edges that are incident to a
vertex of $C_e$, and do not lie on $C_e$, are colored by $\alpha$
and belong to $F$, which and $E(C_e)\cap E(F)=\emptyset$ imply that:

\item[(II)]all maximum $3-$edge-colorable
subgraphs $H'$ of $G$, which can be obtained from the coloring of
$H$, by leaving any edge $g\in E(C_e)$ uncolored, by coloring the
edges of the even path $C_e-g$ $\beta$ and $\gamma$, alternatively,
and leaving the colors of the rest of edges unchanged, satisfy the
condition
\begin{equation*}
|E(F)\cap E(H')|=|E(F)\cap E(H)|\rightarrow min.
\end{equation*}
\end{enumerate}
Now, we consider a proper partial $3-$edge-coloring $\theta$ of the
graph $G$ obtained from the coloring of $H$ by deleting the colors
of the all edges lying on $C_e$. Since $C_e$ is an odd cycle, we
imply that there is an $\alpha-\gamma$ alternating path $P_w$ in the
$3-$edge-coloring $\theta$ that starts from a vertex $w\in V(C_e)$
and does not end on $C_e$. Choose an edge $x=(w,z)\in E(C_e)$, and
let $y$ be the other edge of $C_e$ that is incident to $w$.

Consider a proper partial $3-$edge-coloring of $G$ obtained from
$\theta$ as follows:
\begin{itemize}
\item shift the colors on the path $P_w$, and clear the color of the edge of
$P_e$ that is incident to $w$;

\item color $x$ by $\alpha$, and color the edges of the even path
$C_e-x$ by $\beta-\gamma$ alternatively, starting from the edge $y$.
\end{itemize}

It is not hard to see that the new partial $3-$edge-coloring of $G$
corresponds to a maximum $3-$edge-colorable subgraph $H'$ of $G$,
which due to (II) satisfies
\begin{equation*}
|E(F)\cap E(H')|<|E(F)\cap E(H)|
\end{equation*}contradicting the choice of $H$. The proof of the
theorem \ref{2factorExtension} is completed.
\end{proof}

We suspect that the theorem \ref{2factorExtension} can be generalized as follows:

\begin{conjecture}Let $F$ be any maximal (not necessarily, maximum) matching of a cubic graph $G$. Then there is a maximum
$3-$edge-colorable subgraph $H$ of $G$, such that $E(H)\cup F=E(G)$.
\end{conjecture}
 
 Recently we have proved the following:

\begin{theorem}\label{MainTheoremCubics}\cite{Part1}: For every cubic graph $G$:
\begin{equation*}
\nu _{2}(G)\geq \frac{4}{5}|V(G)| ,\nu _{3}(G)\geq \frac{7}{6}|V(G)|.
\end{equation*}
\end{theorem}

There are graphs attaining bounds of the theorem
\ref{MainTheoremCubics}. The graph from figure \ref{Examples
attaining the bounds}a attains the first bound and the graph from
figure \ref{Examples attaining the bounds}b the second bound.

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=10pc]{Examples.eps}\\
%\includegraphics{Examples.eps}\\
\caption{Examples attaining the bounds of the theorem
\protect\ref{MainTheoremCubics}}\label{Examples attaining the
bounds}
\end{center}
\end{figure}
\end{center}

Note that if there were a cubic graph $G$ attaining the two bounds
at the same time, then we would have:
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)=\frac{4}{5}|V(G)|+\frac{7}{6}|V(G)|=\frac{59}{30}|V(G)|<2|V(G)|.
\end{equation*}
Thus, to show the absence of a cubic graph attaining all the bounds
of theorem \ref{MainTheoremCubics} at the same time, it suffices to
show the following

\begin{theorem}\label{nu2nu3}
For every cubic graph $G$%
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)\geq 2|V(G)|.
\end{equation*}
\end{theorem}
\begin{proof}Suppose that the statement is false, and consider a
minimum counter-example $G$, that is, a cubic graph $G$ with $\nu
_{2}(G)+\nu _{3}(G)< 2|V(G)|$ and $|V(G)|\rightarrow min$. Note that $G$ is
connected.

\begin{claim}\label{TriangleMultiple}Any triangle of $G$ contains a
multiple edge.
\end{claim}
\begin{proof}Suppose that $G$ contains a triangle $T$ that has no
multiple edge. Consider a cubic graph $G'$ obtained from $G$ by
contracting the triangle $T$ to a new vertex. Since $|V(G')|=|V(G)|-2<|V(G)|$, we
imply $\nu _{2}(G')+\nu _{3}(G')\geq 2|V(G')|$. On the other hand, it can be
easily checked that
\begin{gather*}
\nu _{2}(G)\geq\nu_2(G')+2\textrm{ and } \nu _{3}(G)\geq\nu_3(G')+3,
\end{gather*}
(in fact, with a bit more work it can be shown that one always has
equalities here), therefore
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)\geq5+\nu _{2}(G')+\nu' _{3}(G')\geq 5+2|V(G')|>2|V(G)|,
\end{equation*}contradicting the choice of $G$. The proof of the
claim \ref{TriangleMultiple} is completed.
\end{proof}
Before me move to the proof of the next claim, let us also note that
$G$ contains no edge that connects two triangles, since if there
were such an edge, then taking into account that $G$ is connected,
we would have that $G$ is isomorphic to the second graph  from
figure \ref{Examples attaining the bounds}, which clearly satisfies
the statement of the theorem.

\begin{claim}\label{TriangleNeighbourMultiple} Let $x,y,z$ be vertices of a triangle of $G$, and let
$(x,y)$ be its multiple edge (claim \ref{TriangleMultiple}). Assume
that $u$ is the neighbour of $z$ lying outside the triangle. Then
$u$ is not incident to a multiple edge.
\end{claim}
\begin{proof} Suppose that $u$ is incident to a multiple edge and
consider the cubic graph $G'$(figure \ref{TriangleMultipleEdge}).

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=18pc]{TriangleMultipleEdge.eps}\\
%\includegraphics{Examples.eps}\\
\caption{Reducing $G$ to $G'$ in claim
\ref{TriangleNeighbourMultiple}}\label{TriangleMultipleEdge}
\end{center}
\end{figure}
\end{center}

Note that $|V(G)|=|V(G')|+2$, hence $\nu _{2}(G')+\nu _{3}(G')\geq 2|V(G')|$. It can be
easily seen that
\begin{gather*}
\nu _{2}(G)\geq\nu_2(G')+2\textrm{ and } \nu _{3}\geq\nu_3(G')+3,
\end{gather*}
therefore
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)\geq5+\nu _{2}(G')+\nu _{3}(G')\geq 5+2|V(G')|>2|V(G)|,
\end{equation*}contradicting the choice of $G$. The proof of the
claim \ref{TriangleNeighbourMultiple} is completed.
\end{proof}

\begin{claim}\label{TriangleAdjacent} Let $x_1,y_1,z_1$ and $x_2,y_2,z_2$
be vertices of two triangles of $G$, and let $(x_1,y_1),(x_2,y_2)$
be their multiple edges (claim \ref{TriangleMultiple}). Then, there
is no vertex $u$ that is adjacent to both $z_1$ and $z_2$.
\end{claim}
\begin{proof} Suppose that there is such a vertex $u$ and let us
consider the cubic graph $G'$(figure
\ref{TriangleAdjacentTriangles}).

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=18pc]{TriangleAdjacentTriangles.eps}\\
%\includegraphics{Examples.eps}\\
\caption{Reducing $G$ to $G'$ in claim
\ref{TriangleAdjacent}}\label{TriangleAdjacentTriangles}
\end{center}
\end{figure}
\end{center}

Note that $|V(G)|=|V(G')|+4$, hence $\nu _{2}(G')+\nu _{3}(G')\geq 2|V(G')|$. It can be
easily seen that
\begin{gather*}
\nu _{2}(G)\geq\nu_2(G')-2+1+4=\nu_2(G')+3\textrm{ and } \nu
_{3}(G)\geq\nu_3(G')-1+6=\nu_3(G')+5,
\end{gather*}
therefore
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)\geq8+\nu _{2}(G')+\nu_{3}(G')\geq8+2|V(G')|=2|V(G)|,
\end{equation*}contradicting the choice of $G$. The proof of the claim \ref{TriangleAdjacent} is completed.
\end{proof}


\begin{claim}\label{TriangleAdjacentNeighbours} Let $x_1,y_1,z_1$ and $x_2,y_2,z_2$
be vertices of two triangles of $G$, and let $(x_1,y_1),(x_2,y_2)$
be their multiple edges (claim \ref{TriangleMultiple}). Let $u_1$
and $u_2$ be the neighbours of $z_1$ and $z_2$, respectively, that
lie outside the triangles. Then $u_1$ and $u_2$ are not connected by
an edge.
\end{claim}
\begin{proof}First of all note that, due to claim \ref{TriangleAdjacent}, $u_1\neq u_2$.
Suppose that $u_1$ and $u_2$ are adjacent, and let us consider the
cubic graph $G'$(figure \ref{TrianglesAdjacentNeighbours}).

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=18pc]{TrianglesAdjacentNeighbours.eps}\\
%\includegraphics{Examples.eps}\\
\caption{Reducing $G$ to $G'$ in claim \ref
{TriangleAdjacentNeighbours}}\label{TrianglesAdjacentNeighbours}
\end{center}
\end{figure}
\end{center}

Note that $|V(G)|=|V(G')|+6$, hence $\nu _{2}(G')+\nu _{3}(G')\geq 2|V(G')|$. It can be
easily seen that
\begin{gather*}
\nu _{2}(G)\geq\nu_2(G')-1+6=\nu_2(G')+5\textrm{ and } \nu
_{3}(G)\geq\nu_3(G')-1+8=\nu_3(G')+7,
\end{gather*}
therefore
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)\geq12+\nu _{2}(G')+\nu _{3}(G')\geq12+2|V(G')|=2|V(G)|,
\end{equation*}contradicting the choice of $G$. The proof of the claim \ref{TriangleAdjacentNeighbours} is completed.
\end{proof}

\begin{claim}\label{TriangleNeighboursCommonNeighbour} Let $x_1,y_1,z_1$ and $x_2,y_2,z_2$
be vertices of two triangles of $G$, and let $(x_1,y_1),(x_2,y_2)$
be their multiple edges (claim \ref{TriangleMultiple}). Let $u_1$
and $u_2$ be the neighbours of $z_1$ and $z_2$, respectively, that
lie outside the triangles. Then, there is no vertex $w$, that is
adjacent to both $u_1$ and $u_2$.
\end{claim}

\begin{proof}
Suppose that $w$ is adjacent to both  $u_1$ and $u_2$, and let us
consider the cubic graph $G'$(figure \ref{TriangleCommonNeighbour}).

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=18pc]{TriangleCommonNeighbour.eps}\\
%\includegraphics{Examples.eps}\\
\caption{Reducing $G$ to $G'$ in claim \ref
{TriangleNeighboursCommonNeighbour}}\label{TriangleCommonNeighbour}
\end{center}
\end{figure}
\end{center}

Note that $|V(G)|=|V(G')|+6$, hence $\nu _{2}(G')+\nu _{3}(G')\geq 2|V(G')|$. It can be
easily seen that
\begin{gather*}
\nu _{2}(G)\geq\nu_2(G')-1+6=\nu_2(G')+5\textrm{ and } \nu
_{3}(G)\geq\nu_3(G')-1+8=\nu_3(G')+7,
\end{gather*}
therefore
\begin{equation*}
\nu _{2}(G)+\nu _{3}(G)\geq12+\nu _{2}(G')+\nu _{3}(G')\geq12+2|V(G')|=2|V(G')|,
\end{equation*}contradicting the choice of $G$. The proof of the claim \ref{TriangleNeighboursCommonNeighbour} is completed.
\end{proof}

The proved claims imply that the triangles of $G$ are placed
"sufficiently far", and this allows us to complete the proof by
using the odd cycles corresponding to edges that do not lie in some 
maximum $3$-edge-colorable subgraph \cite{SteffenClassification,Steffen}.

Let $H$ be any maximum $3-$edge-colorable subgraph of $G$, and let
$A,B,C$ be its color classes, which are pairwise disjoint matchings
with $|A|+|B|+|C|=|E(H)|=\nu _{3}(G)$. Consider the $5-$tuple
$(A,B,C,A,B)$, and for any $v\in V$ define $\delta(v)$ as the number
of edges that $v$ is incident from this $5-$tuple (edges of $A$ and
$B$ contribute to $\delta(v)$ by two). Note that
\begin{gather*}
2(\nu _{2}(G)+\nu _{3}(G))\geq2[|A|+|B|+|C|+|A|+|B|]=\sum_{v\in
V}{\delta(v)}.
\end{gather*}
Thus, to get the desired contradiction, it suffices to show, that
\begin{gather}
\sum_{v\in V}{\delta(v)}\geq4|V(G)|.\label{MainINEQUALITY}
\end{gather}

Consider the cycles of the uncolored edges of $H$ \cite{SteffenClassification,Steffen}. These
cycles are triangles from figure \ref{MagicTriangles}, whose one
edge is a multiple edge (claim \ref{TriangleMultiple}),

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=15pc]{MagicTriangles.eps}\\
%\includegraphics{Examples.eps}\\
\caption{The triangles corresponding to an edge lying outside a maximum $3$-edge-colorable subgraph}\label{MagicTriangles}
\end{center}
\end{figure}
\end{center}

or are odd cycles from figure \ref{MagicOddCycles} having length at
least five.

\begin{center}
\begin{figure}[h]
\begin{center}
\includegraphics[height=22pc]{MagicOddCycles.eps}\\
%\includegraphics{Examples.eps}\\
\caption{Cycles of length at least
five corresponding to an edge lying outside a maximum $3$-edge-colorable subgraph}\label{MagicOddCycles}
\end{center}
\end{figure}
\end{center}

Note that
\begin{itemize}
\item if a vertex $v\in V$ lies outside these cycles, then it
contributes to the sum (\ref{MainINEQUALITY}) by five;

\item the total contribution of vertices of triangles from
figure \ref{MagicTriangles} (a) and (b) to the sum
(\ref{MainINEQUALITY}) is twelve;

\item the total contribution of vertices of triangles from
figure \ref{MagicTriangles} (c) to the sum (\ref{MainINEQUALITY}) is
eleven;

\item the total contribution of vertices of cycles from
figure \ref{MagicOddCycles} (a) and (b) to the sum
(\ref{MainINEQUALITY}) is $4(2l+1)+2l-2$, where the cycle is assumed
to be of length $2l+1,l\geq2$;

\item the total contribution of vertices of cycles from
figure \ref{MagicOddCycles} (c) to the sum (\ref{MainINEQUALITY}) is
$4(2l+1)+2l-3$, where the cycle is assumed to be of length
$2l+1,l\geq2$.
\end{itemize}

Thus, if we have a triangle with vertices $x,y,z$, whose multiple
edge is $(x,y)$ (claim \ref{TriangleMultiple}), and $u$ is the
neighbour of $z$, lying outside this triangle, then if $u$ does not
lie on either of these odd cycles, then
\begin{equation*}
\delta(x)+\delta(y)+\delta(z)+\delta(u)\geq16=4\cdot4.
\end{equation*}

On the other hand, if a cycle of length $2l+1,l\geq2$ from figure
\ref{MagicOddCycles} contains $r$ vertices, which are adjacent to a
vertex of a triangle from figure \ref{MagicTriangles} (c), then the
proved claims imply that
\begin{equation*}
r\leq\frac{2l+1}{3},
\end{equation*}therefore the total contribution of vertices of these $r$ triangles
and the odd cycle of length $2l+1$ to the sum from
(\ref{MainINEQUALITY}) is at least
\begin{gather*}
\geq4(2l+1)+4\cdot3r+(2l-3)-r\geq4(2l+1)+4\cdot3r+(2l-3)-\frac{2l+1}{3}=\\
4(2l+1)+4\cdot3r+\frac{4l-10}{3}\geq4(2l+1)+4\cdot3r-\frac23
\end{gather*}as $l\geq2$.

Since $\delta(v)$ is integral, we have that the mentioned
contribution is at least
\begin{gather*}
\geq4(2l+1)+4\cdot3r.
\end{gather*}

It is not hard to see that this implies that the inequality
(\ref{MainINEQUALITY}) holds. The proof of the theorem \ref{nu2nu3}
is completed.
\end{proof}


\begin{remark}The graphs from figure \ref{Examples attaining the
bounds} attain the bounds of the theorem, and we suspect that they
are the only connected cubic graphs with this property.
\end{remark}


\begin{thebibliography}{99}

\bibitem{Lov} L. Lovasz, M.D. Plummer, Matching theory, Ann. Discrete Math.
29 (1986).

\bibitem{Part1} V. V. Mkrtchyan, S. S. Petrosyan, G. N. Vardanyan, On disjoint
matchings in cubic graphs, Discr. Math. 2009, submitted, (available
at: http://arxiv.org/abs/0803.0134)

\bibitem{SteffenClassification} E. Steffen, Classifications and characterizations
of snarks, Discr. Math. 188, (1998), pp. 183-203.

\bibitem{Steffen} E. Steffen, Measurements of edge-uncolorability, Discrete
Mathematics 280 (2004), pp. 191-214.

\bibitem{West} D. B. West, Introduction to Graph Theory, Prentice-Hall,
Englewood Cliffs, 1996.

\end{thebibliography}
\end{document}

0909.2767.extracted_bib
\begin{thebibliography}{99}

\bibitem{Lov} L. Lovasz, M.D. Plummer, Matching theory, Ann. Discrete Math.
29 (1986).

\bibitem{Part1} V. V. Mkrtchyan, S. S. Petrosyan, G. N. Vardanyan, On disjoint
matchings in cubic graphs, Discr. Math. 2009, submitted, (available
at: http://arxiv.org/abs/0803.0134)

\bibitem{SteffenClassification} E. Steffen, Classifications and characterizations
of snarks, Discr. Math. 188, (1998), pp. 183-203.

\bibitem{Steffen} E. Steffen, Measurements of edge-uncolorability, Discrete
Mathematics 280 (2004), pp. 191-214.

\bibitem{West} D. B. West, Introduction to Graph Theory, Prentice-Hall,
Englewood Cliffs, 1996.

\end{thebibliography}