\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf David Hartvigsen}
%
%
\medskip
\noindent
%
%
{\bf Maximum Cardinality 1-Restricted Simple 2-Matchings}
%
%
\vskip 5mm
\noindent
%
%
%
%
A {\it simple 2-matching} in a graph is a subgraph all of whose nodes have
degree $1$ or $2$. A simple 2-matching is called $k${\it -restricted} if
every connected component has $>k$ edges. We consider the problem of finding
a $k$-restricted simple 2-matching with a maximum number of edges, which is
a relaxation of the problem of finding a Hamilton cycle in a graph. Our main
result is a min-max theorem for the maximum number of edges in a
1-restricted simple 2-matching. We prove this result constructively by
presenting a polynomial time algorithm for finding a 1-restricted simple
2-matching with a maximum number of edges.
\bye