% gpic macros for use with "gpic -t" as preprocessor for tex, % by Douglas B. West % available for non-commercial use. \def\bu{\bullet} \def\marker{\>\hbox{${\vcenter{\vbox{ \hrule height 0.4pt\hbox{\vrule width 0.4pt height 6pt \kern6pt\vrule width 0.4pt}\hrule height 0.4pt}}}$}\>} \def\gpic#1{#1 % \midinsert\centerline{\box\graph}\endinsert } \medskip\par\noindent{\centerline{\box\graph}} \medskip} %gpic picture, centered with space \documentclass[12pt]{article} \usepackage[left=2cm,right=2cm,top=3cm,bottom=3cm]{geometry} \usepackage{e-jc} \usepackage{amsmath, amssymb, latexsym, amsthm} \usepackage{fullpage} %Environment definitions \newtheorem{theorem}{Theorem} %Defines \begin{theorem} to write "Theorem" \newtheorem{theorem*}{Theorem} %Defines \begin{theorem} to write "Theorem" \newtheorem{proposition}[theorem]{Proposition} %square bracket tells it to count props with theorems \newtheorem{myprop}[theorem]{Proposition} \newtheorem{clm}[theorem]{Claim} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{assumption}{Assumption} \theoremstyle{definition} \newtheorem{property}[theorem]{Property} \newtheorem{solution}[theorem]{Solution} \newtheorem{observation}[theorem]{Observation} \newtheorem{question}{Question} \newtheorem{definition}{Definition} \newtheorem{example}{Example} \theoremstyle{remark} \newtheorem{claim}{Claim} \newtheorem{remark}{Remark} \newenvironment{soln}{\noindent {\it Solution. }}{} \newenvironment{caselist}{\begin{enumerate} \setlength{\itemindent}{0.3in} \renewcommand{\labelenumi}{Case \arabic{enumi}:} \renewcommand{\labelenumii}{Subcase \arabic{enumii}:}}% {\end{enumerate}} %\numberwithin{equation}{section} %(Makes equations numbered 3.1, for example, in section 3) %Figures \usepackage[dvips]{graphicx} \newcommand{\figref}[1]{Figure~\ref{#1}} \graphicspath{{counterfigs/}} \newlength{\mydim} %Shortcuts \newcommand{\bt}{\operatorname{bt}} \newcommand{\RR}{\textbf{r}} \newcommand{\BB}{\mathbb{B}} \newcommand{\ZZ}{\textbf{k}} \newcommand{\QQ}{\textbf{j}} \newcommand{\NN}{\textbf{i}} \newcommand{\ds}{\displaystyle } \newcommand{\is}{\sum_{n = 1}^{\infty}} \newcommand{\cl}[1]{\lceil #1 \rceil} \newcommand{\CL}[1]{\left\lceil #1 \right\rceil} \newcommand{\fl}[1]{\lfloor #1 \rfloor} \newcommand{\FL}[1]{\left\lfloor #1 \right\rfloor} \def\st{\colon\,} \def\cU{{\mathcal U}} \def\B#1{{\bf #1}} \def\esub{\subseteq} \def\nul{\varnothing} \title{Rainbow Matchings of Size $\delta(G)$ in Properly Edge-Colored Graphs} \author{Jennifer Diemunsch$^{1,4}$,\quad Michael Ferrara$^{1,5}$,\quad Allan Lo$^{2,6}$,\quad \\ Casey Moffatt$^1$,\quad Florian Pfender$^3$,\quad and Paul S.\ Wenger$^1$} \begin{document} \maketitle \begin{abstract} A {\it rainbow matching} in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function $f(\delta)$ such that a properly edge-colored graph $G$ with minimum degree $\delta$ and order at least $f(\delta)$ must have a rainbow matching of size $\delta$. We answer this question in the affirmative; an extremal approach yields that $f(\delta) = 98\delta/23< 4.27\delta$ suffices. Furthermore, we give an $O(\delta(G)|V(G)|^2)$-time algorithm that generates such a matching in a properly edge-colored graph of order at least $6.5\delta$. {\bf Keywords:} Rainbow matching, properly edge-colored graphs \end{abstract} %\renewcommand{\thefootnote}%{\fnsymbol{footnote}} \footnotetext[1]{Dept.\ of Mathematical and Statistical Sciences, Univ.\ of Colorado Denver, Denver, CO; email addresses: {\tt jennifer.diemunsch@ucdenver.edu}, {\tt michael.ferrara@ucdenver.edu}, {\tt casey.moffatt@ucdenver.edu}, {\tt paul.wenger@ucdenver.edu}.} \footnotetext[2]{School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK, {\tt s.a.lo@bham.ac.uk}} \footnotetext[3]{ Institut f$\ddot{\text u}$r Mathematik, Univ. Rostock, Rostock, Germany; {\tt Florian.Pfender@uni-rostock.de}.} \footnotetext[4]{Research supported in part by UCD GK12 Transforming Experiences Project, NSF award \# 0742434.} \footnotetext[5]{Research supported in part by Simons Foundation Collaboration Grant \# 206692.} \footnotetext[6]{Research supported in part by Eurupean Research Council Grant \# 258345.} %\renewcommand{\thefootnote}{\arabic{footnote}} \baselineskip18pt \section{Introduction} All graphs under consideration in this paper are simple, and we let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree of a graph $G$, respectively. In this paper, we consider edge-colored graphs and let $c(uv)$ denote the color of the edge $uv$. An edge coloring of a graph is {\it proper} if the colors on edges sharing an endpoint are distinct. An edge-colored graph is {\it rainbow} if all edges have distinct colors. Rainbow matchings are of particular interest given their connection to transversals of Latin squares: each Latin square can be converted to a properly edge-colored complete bipartite graph, and a transversal of the Latin square is a rainbow perfect matching in the graph. Ryser's conjecture~\cite{Ryser} that every Latin square of odd order has a transversal can be seen as the beginning of the study of rainbow matchings. Stein~\cite{Stein} later conjectured that every Latin square of order $n$ has a transversal of size $n-1$; equivalently every proper edge-coloring $K_{n,n}$ has a rainbow matching of size $n-1$. The connection between Latin transversals and rainbow matchings in $K_{n,n}$ has inspired additional interest in the study of rainbow matchings in triangle-free graphs. A thorough survey of rainbow matching and other rainbow subgraphs in edge-colored graphs appears in \cite{KL}. Several results have been attained for rainbow matchings in arbitrarily edge-colored graphs. The {\it color degree} of a vertex $v$ in an edge-colored graph $G$, written $\hat d(v)$, is the number of distinct colors on edges incident to $v$. We let $\hat \delta (G)$ denote the minimum color degree among the vertices in $G$. Wang and Li~\cite{WL} proved that every edge-colored graph $G$ contains a rainbow matching of size at least $\CL{\frac{5\hat\delta(G)-3}{12}}$, and conjectured that a rainbow matching of size $\CL{\hat\delta(G)/2}$ exists if $\hat \delta(G)\ge 4$. LeSaulnier et al.~\cite{LSWW} then proved that every edge-colored graph $G$ contains a rainbow matching of size $\FL{\hat\delta(G)/2}$. Finally, Kostochka and Yancey~\cite{KY} proved the conjecture of Wang and Li in full, and also that triangle-free graphs have rainbow matchings of size $\CL{{2\hat\delta(G)}/{3}}$. Since the edge-colored graphs generated by Latin squares are properly edge-colored, it is of interest to consider rainbow matchings in properly edge-colored graphs. In this direction, LeSaulnier et al.\ proved that a properly edge-colored graph $G$ satisfying $|V(G)|\neq \delta(G)+2$ that is not $K_4$ has a rainbow matching of size $\CL{\delta(G)/2}$. Wang then asked if there is a function $f$ such that a properly edge-colored graph $G$ with minimum degree $\delta$ and order at least $f(\delta)$ must contain a rainbow matching of size $\delta$~\cite{Wang}. As a first step towards answering this question, Wang showed that a graph $G$ with order at least ${8\delta}/{5}$ has a rainbow matching of size $\FL{3\delta(G)/5}$. Since there are $n\times n$ Latin squares with no transversals when $n$ is even (see~\cite{BR,W}), for such a function $f$ it is clear that $f(\delta)>2\delta$ when $\delta$ is even. Furthermore, since maximum matchings in $K_{\delta,n-\delta}$ have only $\delta$ edges (provided $n\ge 2\delta$), there is no function for the order of $G$ depending on $\delta(G)$ that can guarantee a rainbow matching of size greater than $\delta(G)$. In this paper we answer Wang's question from \cite{Wang} in the affirmative, proving that a linear number of vertices in terms of the minimum degree suffices. \begin{theorem} \label{theorem:extremal} If $G$ is a properly edge-colored graph satisfying $|V(G)| \ge 98\delta(G)/23$, then $G$ contains a rainbow matching of size~$\delta(G)$. \end{theorem} Independently, Wang, Zhang, and Liu~\cite{WZL} also answering Wang's question in the affirmative, proving that a properly edge-colored graph $G$ with at least $(\delta(G)^2+4\delta(G)-4)/4$ vertices has a rainbow matching of size $\delta(G)$. The proof of Theorem \ref{theorem:extremal} utilizes extremal techniques akin to those that appear in \cite{KY,LSWW,Wang} and \cite{WL}. We also implement a greedy algorithmic approach to demonstrate that it is possible to efficiently construct a rainbow matching of size $\delta$ in a properly edge-colored graph with minimum degree $\delta$ having order at least $6.5\delta$. To our knowledge, an algorithmic approach of this type has not been previously employed in the study of rainbow matchings. \begin{theorem}\label{theorem:algorithmic} If $G$ is a properly edge-colored graph with minimum degree $\delta$ satisfying $|V(G)|>\frac{13}{2}\delta-\frac{23}{2}+\frac{41}{8\delta}$, then there is an $O(\delta(G)|V(G)|^2)$-time algorithm that produces a rainbow matching of size $\delta$ in $G$. \end{theorem} As a contrast, Itai, Rodeh, and Tanimota~\cite{IRT} proved that determining if an edge-colored graph $G$ has a rainbow matching of size $k$ is NP-complete, even if $G$ is bipartite. More recently, Le and Pfender~\cite{LP} have shown that the problem of determining the maximum size of a rainbow matching in a properly edge-colored graph is NP-hard, even when restricted to properly edge-colored paths. %\noindent If $G$ is triangle-free, a smaller order suffices. %\begin{theorem}\label{trianglefree} %If $G$ is a triangle-free properly edge-colored graph satisfying $|V(G)|>\frac{49}{8}\delta-\frac{21}{2}+\frac{9}{2\delta}$, then $G$ contains a rainbow matching of size $\delta(G)$. %\end{theorem} \section{Proof of Theorem \ref{theorem:extremal}} Let $G$ be a properly edge-colored $n$-vertex graph with minimum degree $\delta$ and $n \ge 98\delta /23$. The theorem holds easily if $\delta\le 2$, so we may assume that $\delta \ge 3$. By way of contradiction, let $G$ be a counterexample with $\delta$ minimized; thus $G$ does not contain a rainbow matching of size~$\delta$. Further, we may assume that $|E(G)|$ is minimized, so in particular the vertices of degree greater than $\delta$ form an independent set, as otherwise we could delete an edge without lowering the minimum degree. We break the proof into a series of simple claims. Let $\Delta(G)=d_1\ge d_2\ge \ldots\ge d_n=\delta$ with $d(v_i)=d_i$ be the degree sequence of $G$. \begin{lemma}\label{lemma:degseq1} For $1\le k\le {2}\delta/3$, there exists an $i\le k$ such that $d_i\le 3\delta-k-2i$. \end{lemma} \begin{proof} Suppose that for some $k\le 2\delta/3$, $d_i\ge 3\delta+1-k-2i$ for all $1\le i\le k$. It follows that $d_i>\delta$ for $i\le k$, and therefore $\{v_1,\ldots,v_k\}$ is an independent set. Delete the vertices $v_1,v_2,\ldots,v_k$ from $G$, and note that $\delta(G\setminus\{ v_1,\ldots,v_k\})\ge \delta-k$. By the minimality of $G$, there exists a rainbow matching $M_k$ of size $\delta-k$ in $G\setminus\{ v_1,\ldots,v_k\}$. The vertex $v_k$ has at most $2(\delta-k)$ neighbors in $M_k$, and is incident to at most $\delta-k$ edges colored with colors occurring in $M_k$. Thus, $v_k$ has a neighbor $w_k\notin V(M_k)$ such that the color of $v_kw_k$ does not occur in $M_k$, and we can extend $M_k$ by adding the edge $v_kw_k$; call the resulting rainbow matching $M_{k-1}$. Note that $w_k\ne v_i$ for $i\le k$ as $\{ v_1,\ldots v_k\}$ is an independent set. The $j$th iteration of this process produces a rainbow matching $M_{k-j}$ of size $\delta-k+j$ that contains $\{v_k,\ldots,v_{k-j+1}\}$. Hence $v_{k-j}$ has at most $2(\delta-k)+j$ neighbors in $M_{k-j}$ and is incident to at most $\delta-k+j$ edges colored with colors occurring in $M_{k-j}$. Thus there is a vertex $w_{k-j}\in N(v_{k-j})$ such that the edge $v_{k-j}w_{k-j}$ extends $M_{k-j}$ to a $(\delta-k+j+1)$-edge rainbow matching $M_{k-(j+1)}$. Continuing in this fashion extends the matching $M_{k}$ by $k$ edges, yielding a rainbow matching of size $\delta$, a contradiction finishing the proof. %Continuing, $v_{k-1}$ has at most $2(\delta-k)+1$ neighbors in $M_{k-1}$ and is incident to at most $\delta-k+1$ edges colored with a color occurring in $M_{k-1}$. %Thus, there is a vertex $w_{k-1}\in N(v_{k-1})$ such that the edge $v_{k-1}w_{k-1}$ extends $M_{k-1}$ a rainbow matching $M_{k-2}$. Continuing in this fashion, we can extend the matching $M_{k}$ by $k$ edges, yielding a rainbow matching of size $\delta$, a contradiction finishing the proof. \end{proof} As a corollary of Lemma~\ref{lemma:degseq1}, we obtain the following. \begin{lemma} \label{lemma:degseq2} For $1\le k\le 2\delta/3$, we have $\sum_{i=1}^k d_i\le k(3\delta-2-k)$, with equality only if $d_1=d_k=3\delta-2-k$. \end{lemma} \begin{proof} We proceed by induction on $k$. For $k=1$, the statement follows from Lemma~\ref{lemma:degseq1}. Now let $k>1$ and let $i\le k$ such that $d_i\le 3\delta-k-2i$. By induction, \[ \sum_{j=1}^{i-1} d_j\le (i-1)(3\delta-1-i),\mbox{ and } \] %by induction, and \[ \sum_{j=i}^k d_j\le (k-i+1)d_i\le (k-i+1)(3\delta-k-2i). \] Thus, \[ \sum_{j=1}^k d_j\le (i-1)(3\delta-1-i)+(k-i+1)(3\delta-k-2i)=3k\delta-k^2-k+1-i(k+2-i)\le k(3\delta-2-k) \] and equality holds only if $i=1$ and $d_1=d_k=3\delta-2-k$. \end{proof} % % % % \begin{lemma} \label{lemma:Delta} % $\Delta(G) \le 3\delta -3$. % \end{lemma} % % \begin{proof} % Let $v$ be a vertex in $G$ such that $d(v) > 3\delta-3$. % By the minimality of $G$, there is a rainbow matching $M$ of size $\delta -1$ in $G -v$. % Recall that $G$ is properly edge-colored and $d(v) > 3\delta-3$, so $v$ has at least $\delta$ neighbors that are not in $V(M)$. % Thus $v$ has a neighbor $u$ not in $V(M)$ such that the color $c(uv)$ does not appear in $M$, and $M \cup \{uv\}$ is a rainbow matching of size $\delta$. % \end{proof} %A subgraph $H$ of $G$ is {\it monochromatic} if every edge in $H$ has the same color. % \begin{clm} \label{clm:a} % The largest color class in $G$ contains at least two edges. % \end{clm} % % \begin{proof} % It suffices to prove that $G$ has a matching of size $\delta$, since two edges in such a matching must have the same color. % %If there is no monochromatic matching of size two, then $G$ is rainbow. % %Thus, it is enough to show that $G$ contains a matching of size~$\delta$. % Let $G_1$ be a component of $G$. Then either $G_1$ contains a path of length $2\delta-1$, % or a hamiltonian path. % This is an easy consequence of the standard proof (see e.g.~\cite{Die}) of Dirac's minimum degree condition for hamiltonian cycles \cite{Dir}. % % A path of length $2\delta-1$ contains a matching of size $\delta$, % %and so does a hamiltonian cycle if $|G_1|\ge 2\delta$, % so we may assume that every component of $G$ has hamiltonian path of length at most $2\delta-2$. As $|G|>2\delta-1$, $G$ must contain at least two components. Since every component contains at least $\delta+1$ vertices, the hamiltonian paths in each component contain matchings of size at least $\delta/2$, combining to a matching of size $\delta$. % % % % % % % % Assume that $G$ has no such matching, and let $M= \{ x_i y_i : 1 \le i \le m \}$ is a maximum matching in $G$ with $m\le \delta-1$. % % %If $m \ge \delta$, then we are done. % % For each vertex $v \notin V(M)$, the neighborhood of $v$ must lie in $V(M)$. % % Furthermore, since $d(v) \ge \delta$, there exists an integer $i\in\{1,\ldots,m\}$ such that both $x_iv$ and $y_iv$ are edges. % % As $|V(G)-V(M)| \ge \delta+2$, there exists an integer $i\in\{1,\ldots,m\}$ and vertices $v,v' \notin V(M)$ such that $v \ne v'$ and $x_iv, y_iv, x_iv'$ and $y_iv'$ are edges. % % Thus, $(M \cup \{x_iv, y_iv'\}) \setminus \{x_iy_i\}$ is a matching of size $m+1$, contradicting the maximality of $M$. % \end{proof} %Fix a monochromatic matching $M_0$ of maximal size with $e(M) =a$. Let $C$ be a maximum color class in $G$ and let $|C|=a$. By the minimality of $G$, there exists a rainbow matching $M= \{ x_i y_i : 1 \le i \le \delta -1 \}$ of size~$\delta-1$ in $G -C$. Without loss of generality, we may assume that $c(x_iy_i) = i $ for $1 \le i \le \delta - 1$ and the edges in $C$ have color~$\delta$. Let $W = V(G) \backslash V(M)$; observe that $|W| = n - 2(\delta -1)$. If there is an edge $e$ in $G[W]$ with $c(e)\notin\{1,\ldots,\delta-1\}$ then we can add $e$ to $M$ to obtain a rainbow matching of size~$\delta$. Thus we may assume that every edge whose color is not in~$\{1, \dots, \delta-1\}$ has an endpoint in $V(M)$. An edge $uv$ is {\it good} if its color is not in~$\{1, \dots, \delta-1\}$ and one of its endpoints is in~$W$. A vertex $v \in V(M)$ is {\it good} if $v$ is incident with at least seven good edges. %If there exists a good edge $uv$ in $G[W]$ (the induced edge-colored subgraph of $G$ on $W$), then $M \cup \{uv\}$ is a rainbow matching of size~$\delta$. %Thus, we may assume that every good edge is incident with~$V(M)$, so every good edge has an endpoint in $V(M)$ and an endpoint in $W$. \begin{clm} \label{clm:goodvertex} For $i\in \{1, \dots, \delta-1\}$, if $x_i$ is incident with at least three good edges, then no good edge is incident with~$y_i$, and vice versa. \end{clm} \begin{proof} Suppose that $y_iu$ is a good edge. If $x_i$ is incident with at least three good edges, then $x$ has a neighbor $w$ such that $vw$ is a good edge, $w\neq u$, and $c(x_iw) \ne c(y_iu)$. Thus $(M \cup \{x_iw, y_iu\}) \backslash \{x_iy_i\}$ is a rainbow matching of size $\delta$, a contradiction. \end{proof} By Claim~\ref{clm:goodvertex}, we may assume without loss of generality that $\{x_1, \dots, x_r\}$ is the set of good vertices for some $r\ge 0$. Let $W' = W \cup \{ y_1, \dots, y_r\}$. \begin{clm} \label{clm:goodedge} No edge $uv$ in $G[W']$ has color in $\{1, \dots, r\}$. \end{clm} \begin{proof} By way of contradiction, assume that there is an edge $uv$ in $G[W']$ such that $c(uv)\in\{1,\ldots,r\}$. Let $M'$ be the subset of $M$ consisting of the edge with color $c(uv)$ and any edges with an endpoint in $\{u,v\}$. There are at most three such edges (the edge with color $c(uv)$ and possibly one for each endpoint); without loss of generality, let $M'=\{x_1y_1,\ldots,x_ty_t\}$ (here $1\le t\le 3$). Note that $x_j$ is a good vertex for $1\le j\le t$. Thus there are distinct vertices $w_1,\ldots,w_t$ such that $x_jw_j$ is a good edge for $1\le j\le t$ and the colors on the edges $uv,x_1w_1,\ldots,x_tw_t$ are distinct. Thus $(M \cup \{uv,x_1w_1,\ldots,x_tw_t\}) \backslash \{x_1y_1,\ldots,x_ty_t\}$ is a rainbow matching of size $\delta$, a contradiction. % % % %If $u,v \in W$, then there exists a vertex $w \in W$ such that $x_1w$ is good and $w \ne u,v$. %Thus $(M \cup \{uv,x_1w\}) \backslash \{x_1y_1\}$ is a rainbow matching of size~$\delta$, a contradiction. %Next assume that $u \in W$ and $v \notin W$. %Hence $r \ge 2$ and without loss of generality let $v = y_2$. %There exist distinct vertices $w_1,w_2 \in W \backslash \{u \}$ such that $x_1w_1$ and $x_2w_2$ are good edges and $c(x_1w_1) \ne c(x_2w_2)$. %Thus $(M \cup \{y_2u, x_1w_1, x_2w_2\}) \backslash \{x_1y_1, x_2y_2\}$ is a rainbow matching of size~$\delta$, a contradiction. %Finally, assume that $u,v \notin W$. %Hence $r \ge 3$ and wihtout loss of generality $u = y_2$ and $v = y_3$. %Since $x_1$, $x_2$ and $x_3$ are good, there exist distinct vertices $w_1,w_2,w_3 \in W$ such that $x_1w_1$, $x_2w_2$ and $x_3w_3$ are good edges with distinct colors. %Thus, $(M \cup \{y_2y_3, x_1w_1, x_2w_2, x_3w_3\}) \backslash \{x_1y_1, x_2y_2, x_3y_3\}$ is a rainbow matching of size $\delta$, a contradiction. \end{proof} An edge $uv$ is \emph{nice} if its color is not in~$\{r+1, \dots, \delta-1\}$ and one of its endpoints is in $W'$. Note that every good edge is nice. Recall that every good edge has an endpoint in~$V(M)$. By Claim~\ref{clm:goodvertex} and Claim~\ref{clm:goodedge}, no nice edge lies in $G[W']$. Hence, every nice edge joins vertices in $W'$ and $V(G) \backslash W'$. A vertex $v \in V(M) \backslash \{ x_1,\dots,x_r,y_1, \dots,y_r\}$ is \emph{nice} if $v$ is incident with at least seven nice edges. Note that if there is no good vertex (i.e. $r=0$), then the definitions of good and nice vertices are the same and so there is also no nice vertex. Next, we prove analogues of Claim~\ref{clm:goodvertex} and Claim~\ref{clm:goodedge} for nice vertices and edges. \begin{clm} \label{clm:nicevertex} For $i\in\{r+1,\ldots,\delta-1\}$, if $x_i$ is incident with at least three nice edges, then no nice edge is incident with~$y_i$, and vice versa. \end{clm} \begin{proof} Suppose $y_iu$ is a nice edge for some $i\in\{r+1,\ldots,\delta-1\}$. If $x_i$ is incident to at least three nice edges, then $x_i$ has a neighbor $v$ such that $x_iv$ is a nice edge, $v\neq u$, and $c(x_iv)\neq c(y_iu)$. Let $M'$ be the subset of $M$ consisting of edges with an endpoint in $\{u,v\}$ or a color in $\{c(x_iv),c(y_iu)\}$. There are at most four such edges (possibly one with each endpoint and one with each color); without loss of generality, let $M'=\{x_1y_1,\ldots,x_ty_t\}$ (here $0\le t\le 4$). Note that $x_j$ is a good vertex for $1\le j\le t$. Thus there are distinct vertices $w_1,\ldots,w_t$ such that $x_jw_j$ is a good edge for $1\le j\le t$ and the colors on the edges $x_iv,y_iu,x_1w_1,\ldots,x_tw_t$ are distinct. Thus $(M \cup \{x_iv,y_iu,x_1w_1,\ldots,x_tw_t\}) \backslash \{x_iy_i,x_1y_1,\ldots,x_ty_t\}$ is a rainbow matching of size $\delta$, a contradiction. % %Suppose the contrary, so $x_i$ is incident with at least three nice edges and $y_iu$ is a nice edge for some $r+1 \le i \le \delta-1$. %Here, we only consider one particular case as each remaining case can be verified using a similar argument. %Suppose that $r \ge 4$, $u=y_1$ and $c(y_iy_1) = 2$. %Since $x_i$ is nice, there exists a vertex $v \in W'$ such that $x_iv$ is nice, $v \ne u=y_1$ and $c(x_iv) \ne c(y_iy_1) = 2$. %Assume that $v = y_3$ and $c(x_iy_3 )=4$ . %Recall that $x_1, \dots, x_4$ are good vertices, so each is incident to at least seven good edges. %Thus, there exist distinct vertices $w_1,w_2,w_3,w_4 \in W$ such that $x_1w_1$, $x_2w_2$, $x_3w_3$ and $x_4w_4$ are good edges with distinct colors. %Therefore, $M \cup \{y_iy_1, x_iy_3 ,x_1w_1, x_2w_2, x_3w_3,x_4w_4\} \backslash \{x_1y_1, x_2y_2, x_3y_3,x_4y_4,x_iy_i\}$ is a rainbow matching of size $\delta$, a contradiction. \end{proof} % % By Claim~\ref{clm:nicevertex}, we may assume that $\{x_{r+1}, x_{r+2}, \dots, x_{r+s}\}$ is the set of nice vertices for some $s \ge 0$. \begin{clm} \label{clm:niceedge} No edge $uv$ in $G[W']$ has color in $\{1, \dots, r+s\}$. \end{clm} \begin{proof} By Claim~\ref{clm:goodedge}, the claim holds if $s =0$. Assume that $s \ge 1$, and consequently $r \ge 1$. Without loss of generality, suppose that there is an edge $uv$ in $G[W']$ with $c(uw) =r+1$. Because $x_{r+1}$ is nice, it has a neighbor $v'$ in $W'$ such that $x_{r+1}v'$ is a nice edge and $v'\neq u,v$. %The rest of the proof is essentially the same as the proofs of Claims~\ref {clm:goodedge} and~\ref{clm:nicevertex}. Let $M'$ be the subset of $M$ consisting of those edges an endpoint in $\{u,v,v'\}$ or color $c(x_{r+1}v')$. Again there are at most four edges in $M'$ and we let $M'=\{x_1y_1,\ldots,x_ty_t\}$. Defining $w_1,\ldots,w_t$ as before, $(M \cup \{uv,x_{r+1}v',x_1w_1,\ldots,x_tw_t\}) \backslash \{x_{r+1}y_{r+1},x_1y_1,\ldots,x_ty_t\}$ is a rainbow matching of size $\delta$, a contradiction. % % %Again, we only consider one particular case as each remaining case can be verified using a similar argument. %Suppose that $r \ge 4$, $u=y_1$ and $v = y_2$. %Since $x_{r+1}$ is nice, there exists a vertex $v' \in W'$ such that $v'x_{r+1}$ is a nice edge. %Assume that $v = y_3$ and $c(x_{r+1}y_3 )=4$. %Recall that $x_1, \dots, x_4$ are good vertices, so each is incident to at least seven good edges. %Thus, there exist distinct vertices $w_1,w_2,w_3,w_4 \in W$ such that $x_1w_1$, $x_2w_2$, $x_3w_3$ and $x_4w_4$ are good edges with distinct colors. %Therefore, $M \cup \{y_1y_2, x_{r+1}y_3 ,x_1w_1, x_2w_2, x_3w_3,x_4w_4\} \backslash \{x_1y_1, x_2y_2, x_3y_3,x_4y_4,x_{r+1}y_{r+1}\}$ is a rainbow matching of size $\delta$, a contradiction. \end{proof} Next, we count the number of nice edges in $G$. \begin{clm} \label{clm:maxniceedges} There are at most $\max\left\{ (3\delta -8-r+s)r + 6(\delta - 1), \left( 7\delta/3-7+s\right) r + 6(\delta - 1)\right\}$ nice edges in $G$. \end{clm} \begin{proof} Recall that $V(G) \setminus W' = \{x_1, \dots, x_{\delta-1}, y_{r+1}, \dots, y_{\delta-1} \}$ and every nice edge joins vertices from $W'$ and $V(G) \setminus W'$. If $r\le 2\delta/3$, then the set of good vertices is incident to at most $r(3\delta-2-r)$ nice edges by Lemma~\ref{lemma:degseq2}. Similarly, if $r\ge 2\delta /3$, then the set of good vertices is incident to at most $r(3\delta-2-\lfloor 2\delta / 3\rfloor)\le r(7\delta/3-1)$ nice edges. %For $i\in\{1,\ldots,r\}$, $x_i$ is incident to at most $3\delta-3$ nice edges as $\Delta(G) \le 3\delta-3$. For $i\in\{r+1,\ldots,r+s\}$, Claim~\ref{clm:nicevertex} implies that $x_i$ is incident to at most $r+6$ nice edges and $y_i$ is incident to none. For $i\in\{r+s+1,\ldots,\delta -1\}$, by Claim~\ref{clm:nicevertex} there are at most six nice edges with an endpoint in $\{x_i,y_i\}$. Therefore, the number of nice edges is at most \[ (3\delta-2-r)r + (r+6)s + 6(\delta - 1-r-s) = (3\delta -8-r+s)r + 6(\delta - 1)\mbox{ if }r\le 2\delta/3, \] and \[ \left( 7\delta/3-1\right) r + (r+6)s + 6(\delta - 1-r-s) = \left( 7\delta/3-7+s\right) r + 6(\delta - 1)\mbox{ if }r\ge 2\delta/3.\qedhere \] \end{proof} Recall that $C$ is the color class with color~$\delta$, $|C|=a$, and $C$ is a maximum size color class. Therefore there are at least $2(a-\delta+1)$ vertices in $W$ incident to an edge in $C$. Since every edge in $C$ has an endpoint in $V(M)$ it follows that there are at least $2(a - \delta+1)$ vertices in $V(M)$ joined to $W$ by edges in $C$. Without loss of generality, let $\{r+s+1, \dots, r+s+t\}$ be the set of indices $i\in\{r+s+1,\ldots,\delta-1\}$ such that $x_i$ or $y_i$ is incident to an edge in $C$. %there exists $w \in W$ with $c(x_iw) = \delta$ or $c(y_iw) = \delta$. %Without loss of generality, we may assume that $r+s+1, \dots, r+s+t$ are such~$i$. By Claim~\ref{clm:goodvertex} and Claim~\ref{clm:nicevertex}, we have \begin{align} t \ge a - \delta+1 - \frac{r+s}{2}\mbox{ and }r+s+t \le \delta -1.\label{eqn:t} %\textrm{$t \ge a - \delta+1 - \frac{r+s}{2}$ and $r+s+t \le \delta -1$.} \label{eqn:t} \end{align} \begin{clm} \label{clm:t} For $i\in\{r+s+1,\ldots,r+s+t\}$, there is at most one edge of color~$i$ in $G[W]$. \end{clm} \begin{proof} Suppose $uv$ and $u'v'$ are edges of color $i$ in $G[W]$ for some $i\in \{r+s+1,\ldots,r+s+t\}$. Without loss of generality, we may assume that there exists $w \in W$ such that $c(x_{i}w) = \delta$ and $w\neq u,v$. Hence, $(M \cup \{uv, x_{i}w\}) \setminus \{x_{i}y_{i}\}$ is a rainbow matching of size $\delta$, a contradiction. \end{proof} Now we count the number of nice edges from $W'$ to $V(G) \setminus W'$. Recall that each color class in $G$ contains at most $a$ edges. By Claim~\ref{clm:niceedge}, there is no edge in $G[W']$ of color~$i\in\{r+1,\ldots,r+s\}$. Thus, for $i\in\{r+1,\ldots,r+s\}$ there are at most $a-1$ vertices in $W'$ that are incident with an edge of color~$i$. Since every color class has size at most $a$, for $i\in\{r+s+1,\ldots,\delta-1\}$ there are at most $2(a-1)$ vertices in $W'$ that are incident with an edge of color~$i$. Furthermore for $i\in\{r+s+1,\ldots,r+s+t\}$, Claim~\ref{clm:t} implies that there are at most $a$ vertices in $W$ that are incident with an edge of color~$i$. Since $W' \setminus W =\{ y_1, \dots, y_r\}$, it follows that for $i\in\{r+s+1,\ldots,r+s+t\}$ there are at most $\min\{a+r,2(a-1)\}$ vertices in $W'$ that are incident with an edge of color~$i$. %Furthermore, since each color class has size at most $a$, %Since every color class has size at most $a$, for $i\in\{r+s+t+1,\ldots,\delta-1\}$ there are at most $2(a-1)$ vertices in $W'$ that are incident with an edge of color~$i$. It then follows, using the fact that $|W'| = |W|+r = n - 2(\delta-1)+r$ and~\eqref{eqn:t}, that the number of nice edges from $W'$ to $V(G) \setminus W'$ is at least \begin{align} & \delta|W'| -(a-1)(2\delta -2 - 2r-s-2t)-\min\{ a+r,2(a-1)\}t \nonumber\\ =~ & \delta n - 2\delta(\delta-1) +\delta r - (a-1)(2\delta-2-2r-s)+\max\{a-r-2,0\}t. \nonumber %\\ % \ge~ & \delta n - 2\delta(\delta-1) - (a-1)(2\delta-2-2r)+(a-2)t +(r+1)r. \nonumber \end{align} We first consider the case when $r\le 2\delta/3$. Applying the upper bound of $(3\delta -8-r+s)r + 6(\delta - 1)$ nice edges from Claim~\ref{clm:maxniceedges}, we obtain \begin{align} \delta n &\le& (2\delta -8-r+s)r + 2(\delta +3)(\delta - 1) + (a-1)(2\delta-2-2r-s)-\max\{a-r-2,0\}t. \label{eqn:|G|} \end{align} To finish the proof we bound the right hand side of~\eqref{eqn:|G|} to obtain a contradiction. Note that the coefficient of $t$ is nonpositive. % by Claim~\ref{clm:a}. Thus, the right hand side of~\eqref{eqn:|G|} is maximized when $t$ is minimized. By~\eqref{eqn:t}, $t \ge \max\{a- \delta +1 -(r+s)/2,0\}$. If $a \le \delta -1 +(r+s)/2$, then we let $t=0$. The coefficient of $a$ is nonnegative, and %becomes $2 \delta - 2- 2r \ge 2(\delta -1 - r) \ge 0$. thus~\eqref{eqn:|G|} is maximized when $a$ is maximized; hence we assume $a=\delta -1 +(r+s)/2$. Substituting for $a$ yields a negative quadratic in $s$ that is maximized when $s=1-r/2$. Since $s$ is a nonnegative integer and $s=0$ if $r=0$,~\eqref{eqn:|G|} is maximized at $s=0$, which yields \begin{align} %\delta n \le 2(2 \delta+1) (\delta -1) + (2 \delta -7 -2r)r- (3r+s-2)s/2.\nonumber\\ \delta n \le 2(2 \delta+1) (\delta -1)+( \delta-5-2r)r.\nonumber \end{align} % Recall that if $s \ge 1$, then $r \ge 1$. % Hence, $(3r+s-2)s \ge 0$ and so % \begin{align} % \delta n \le & 2(2 \delta+1) (\delta -1) + (2 \delta -6 -3r)r.\nonumber % % \le 9\delta^2/2 -11\delta/2 +33/8 \nonumber % \end{align} This is maximized when $r= (\delta-5)/4$, yielding $n\le 33\delta/8 -13/4 +9/(8\delta)$, %Since $\delta\ge 2$ this is a contradiction. If $a>\delta -1 +r/2$, we let $t = a- \delta +1 -r/2$. Since $t>0$, it follows that $r+s\le \delta-2$. Thus $a-r-2>\delta-3-(r-s)/2\ge \delta-3-(\delta-2)/2 = \delta/2-2$. As $\delta\ge 3$ and $a-r-2$ is an integer, $\max\{a-r-2,0\}=a-r-2$. Therefore the coefficient of $s$ in~\eqref{eqn:|G|} is nonpositive and we may assume that $s=0$. Consequently, \eqref{eqn:|G|} becomes \begin{align} \delta n \le & (3\delta -1 - r/2-a )a +(\delta -6 -3r/2)r +2 (\delta^2 -1). \nonumber \end{align} %This is maximized when $a=(3\delta -1)/2 - (3r+s)/4$. The right hand side is maximized when $a=3\delta/2-1/2-r/4$, so \[ \delta n \le \frac{1}{16} (-28 + 68 \delta^2 - 24 \delta + 4\delta r - 92 r - 23 r^2), \] which is maximized when $r=2\delta/23-2$. This yields \[ n\le 98 \delta/23-2 + 4/\delta, \] a contradiction. % ========= % % If $(3\delta -1)/2 - (3r+s)/4 \le \delta -1 +(r+s)/2$, then the right hand side is maximized when $a = \delta -1 +(r+s)/2$, which corresponds to the case when $a \le \delta -1 +(r+s)/2$ and so we are done. % % Hence, we may assume that $(3\delta -1)/2 - (3r+s)/4 > \delta -1 +(r+s)/2$, so % % \begin{align} % % {5r+3s} < 2(\delta +1). \label{eqn:r} % % \end{align} % Letting $a = (3\delta -1)/2 - (3r+s)/4$ yields % \begin{align*} % \delta n \le & \frac{1}{4}\left(3\delta -1 - \frac{3r+s}{2}\right)^2 +(3 \delta -8 -2r)r +2 (\delta+1)(\delta -1) \\ % = & \left( -\frac{23r}{16}+\frac{3\delta}4 - \frac{29}4\right)r + \left(\frac{3r}{8} +\frac{s}{16} -\frac{3\delta}4 + \frac14 \right)s + \frac{17 \delta^2}4 - \frac{3\delta}2 -\frac74 \\ % = & \left( -\frac{23r}{16}+\frac{3\delta}4 - \frac{29}4\right)r + \left(\frac{6r+s+4-12\delta}{16}\right)s + \frac{17 \delta^2}4 - \frac{3\delta}2 -\frac74 % % \le & \left( -\frac{7r}{16}+\frac{3\delta}4 - \frac{33}4\right)r + \left(\frac{3(5r+3s)}{40} -\frac{3\delta}4 + \frac14 \right)s + \frac{17 \delta^2}4 - \frac{3\delta}2 -\frac74 \\ % % \le & \left( -\frac{7r}{16}+\frac{3\delta}4 - \frac{33}4\right)r + \frac{(2-3\delta)s}{5} + \frac{17 \delta^2}4 - \frac{3\delta}2 -\frac74 \\ % % \le & \left( -\frac{7r}{16}+\frac{3\delta}4 - \frac{33}4\right)r + \frac{17 \delta^2}4 - \frac{3\delta}2 -\frac74. % \end{align*} % Since $\delta\ge r+s+1$, this is maximized when $s=0$, yielding % \begin{align} % \delta n \le \left( -\frac{23r}{16}+\frac{3\delta}4 - \frac{29}4\right)r + \frac{17 \delta^2}4 - \frac{3\delta}2 -\frac74. \label{eqn:dn} % \end{align} % The right hand side of~\eqref{eqn:dn} is maximized at $r=2(29 - 3 \delta)/23 \le 2$, % yielding % \[ % % n \le 17 \delta/4 -22/\delta<13\delta/3 - 5/2, % n \le 17 \delta/4 - \min \{2, 22/\delta \} < 13 \delta /3 - 2 , % \] % a contradiction. % . %$r = 6(\delta-11)/7$. % However, %by~\eqref{eqn:r} % we have $0\le r \le 2\delta /3$, and therefore the bound is maximized at $r=1$ if $\delta=2 $, and at $r=2(29 - 3 \delta)/23$ if $3\le r\le 9$, and at $r=0$ if $\delta\ge 10$. % Therefore, % \begin{align*} % n \le % \begin{cases} % 81/32 & \textrm{if $\delta = 2$}\\ % 17 \delta/4 -22/\delta & \textrm{if $3 \le \delta \le 9$}\\ % 37\delta/9-19/3 -7/(4\delta) & \textrm{if $\delta \ge 10$.} % \end{cases} % \end{align*} % In all cases, $n< \frac{13}{3}\delta - 3$, a contradiction. % This completes the proof of Theorem~\ref{theorem:extremal}. To complete the proof of the theorem, we are left with the case $r\ge 2\delta/3$. Similarly to~\eqref{eqn:|G|}, since we have at most $\left( 7\delta/3-7+s\right) r + 6(\delta - 1)$ nice edges in $G$ by Claim~\ref{clm:maxniceedges}, we have \begin{align} \delta n \le~& \left( 4\delta/3-7+s\right) r + 2(\delta +3)(\delta - 1) + (a-1)(2\delta-2-2r-s) -\max\{a-r-2,0\}t.\label{eqn:|G|2} %\\ %\le~& 2(\delta +2a+1)(\delta - 1) +a+2+\left( 4\delta/3-2a-4\right) r \label{eqn:|G|2} \end{align} % To finish the proof we bound the right hand side of~\eqref{eqn:|G|} to obtain a contradiction. % Note that $-(a-2)$, the coefficient of $t$, is nonpositive by Claim~\ref{clm:a}. Again, the right hand side of~\eqref{eqn:|G|2} is maximized when $t$ is minimized. If $a \le \delta -1 +(r+s)/2$, %then we let $t=0$. %The coefficient of $a$ becomes $2 \delta - 2- 2r -s \ge 2(\delta -1 - r-s) \ge 0$. then \eqref{eqn:|G|2} is maximized when $t=0$ and $a = \delta -1 +r/2$. Again we may assume that $s=0$, yielding % \begin{align} % %\delta n \le 2(2 \delta+1) (\delta -1) + (2 \delta -7 -2r)r- (3r+s-2)s/2.\nonumber\\ % \delta n \le 2(2 \delta+1) (\delta -1)+(4 \delta/3+1-2r)r- (3r+s-2)s/2.\nonumber % \end{align} %with $(3r+s-2)s \ge 0$ \begin{align} \delta n \le & -2 + 4 \delta^2 -2\delta+ r(\delta /3 - 4 - r).\nonumber %2(2 \delta+1) (\delta -1) + (4 \delta/3-5-2r)r.\nonumber % \le 9\delta^2/2 -11\delta/2 +33/8 \nonumber \end{align} This is maximized when $r= \delta/6-2$, yielding $n\le 145\delta/36-8/3+6/\delta$, a contradiction. If $a > \delta -1 +(r+s)/2$, we let $t = a- \delta +1 -(r+s)/2$ and again we may assume that $s=0$. Then, \eqref{eqn:|G|2} becomes \begin{align} % \delta n \le & \frac16 (-6 a^2 + 3 a ( 6 \delta - r-2)+ 12 \delta^2 + 2 \delta r - % 3 (4 + 10 r + r^2)),\\ \delta n \le&\frac16 (-6 a^2 + 3 a ( 6 \delta -2)+ 12 \delta^2 - (3a + 30 + 3r-2\delta)r-12), \nonumber \end{align} which is maximized when $r$ is minimized. Since we have assumed that $r\ge 2\delta/3$, we have $r=2\delta/3$ and we are back in the case $r\le2\delta/3$, finishing the proof of the theorem. \qed \section{Proof of Theorem \ref{theorem:algorithmic}} We proceed by induction on $\delta(G)$. The result is trivial if $\delta(G)= 1$. We assume that $G$ is a graph with minimum degree $\delta>1$ and order greater than $\frac{13}{2}\delta-\frac{23}{2}+\frac{41}{8\delta}$. \begin{lemma}\label{colorclass} If $G$ has a color class containing at least $2\delta-1$ edges, then $G$ has a rainbow matching of size $\delta$. \end{lemma} \begin{proof} Let $C$ be a color class with at least $2\delta-1$ edges. By induction, there is a rainbow matching $M$ of size $\delta-1$ in $G-C$. There are $2\delta-2$ vertices covered by the edges in $M$, thus one of the edges in $C$ has no endpoint covered by $M$, and the matching can be extended. \end{proof} It is also useful to note that we also have the following, which is identical to Lemma \ref{lemma:degseq1} when $k=1$. \begin{lemma}\label{maxdeg} If $G$ satisfies $\Delta(G)>3\delta-3$, then $G$ has a rainbow matching of size $\delta$. \end{lemma} We begin by preprocessing the graph so that each edge is incident to at least one vertex with degree $\delta$. To achieve this, arbitrarily order the edges in $G$ and process them in order. If both endpoints of an edge have degree greater than $\delta$ when it is processed, delete that edge. In the resulting graph, every edge is incident to a vertex with degree $\delta$. Furthermore, by Lemma~\ref{maxdeg} we may assume that $\Delta(G)\le 3\delta-3$; thus the degree sum of the endpoints of any edge is bounded above by $4\delta-3$. After preprocessing, we begin the greedy algorithm. In the $i$th step of the algorithm, a smallest color class is chosen (without loss of generality, color $i$), and then an edge $e_i$ of color $i$ is chosen such that the degree sum of the endpoints is minimized. All the remaining edges of color $i$ and all edges incident with the endpoints of $e_i$ are deleted. The algorithm terminates when there are no edges in the graph. We assume that the algorithm fails to produce a matching of size $\delta$ in $G$; suppose that the rainbow matching $M$ generated by the algorithm has size $k$. We let $R$ denote the set of vertices that are not covered by $M$. Let $c_i$ denote the size of the smallest color class at step $i$. Since at most two edges of color $i+1$ are deleted in step $i$ (one at each endpoint of $e_i$), we observe that $c_{i+1}+2\ge c_i$. Otherwise, at step $i$ color class $i+1$ has fewer edges. Let step $h$ be the last step in the algorithm in which a color class that does not appear in $M$ is completely removed from $G$. It then follows that $c_h\le 2$, and in general $c_i\le 2(h-i+1)$ for $i\in [h]$. Let $f_i$ denote the number of edges of color $i$ deleted in step $i$ with both endpoints in $R$. Since $f_i< c_i$, we have $f_i\le 2(h-i)+1$ for $i\in[h]$. Note that after step $h$, there are exactly $k-h$ colors remaining in $G$. By Lemma~\ref{colorclass}, color classes contain at most $2\delta-2$ edges, and therefore the last $k-h$ steps remove at most $(k-h)(2\delta-2)$ edges. Furthermore, for $i>h$, the degree sum of the endpoints of $e_i$ is at most $2(\delta-1)$. For $i\in[h]$, let $x_i$ and $y_i$ be the endpoints of $e_i$, and let $d_i(v)$ denote the degree of a vertex $v$ at the beginning of step $i$. Let $\mu_i = \max\{0,d_i(x_i)+d_i(y_i)-2\delta\}$; note that $2\delta\le 2\delta+\mu_i\le 4\delta-3$. Thus, at step $i$, at most $2\delta+\mu_i+f_i-1$ edges are removed from the graph. Since the algorithm removes every edge from the graph, we conclude that \begin{equation}\label{ub} |E(G)|\le (k-h)(2\delta-2)+\sum_{i=1}^{h} (2\delta+\mu_i+f_i-1). \end{equation} %\noindent Since $\mu_i+f_i\ge 0$, this bound is maximized when $h=k$ so we may assume that a color class that does not appear in $M$ is completely removed from $G$ at step $k$. %Consequently, $f_i\le 2(k-i)+1$ for $i\in[k]$. %Furthermore, we obtain the following simplified bound: % %\begin{equation}\label{ub} %|E(G)|\le \sum_{i=1}^{k}(2\delta+\mu_i+f_i-1). %\end{equation} We now compute a lower bound for the number of edges in $G$. Since the degree sum of the endpoints of $e_i$ in $G$ is at least $2\delta+\mu_i$, we immediately obtain the following inequality: $$\frac{n\delta+\sum_{i\in[h]}\mu_i}{2}\le |E(G)|.$$ If $f_i>0$ and $\mu_i>0$, then there is an edge with color $i$ having both endpoints in $R$. Since this edge was not chosen in step $i$ by the algorithm, the degree sum of its endpoints is at least $2\delta+\mu_i$, and one of its endpoints has degree at least $\delta+\mu_i$. For each value of $i$ satisfying $f_i>0$, we wish to choose a representative vertex in $R$ with degree at least $\delta+\mu_i$. Since there are $f_i$ edges with color $i$ having both endpoints in $R$, there are $f_i$ possible representatives for color $i$. Since a vertex in $R$ with high degree may be the representative for multiple colors, we wish to select the largest system of distinct representatives. Suppose that the largest system of distinct representatives has size $t$, and let $T$ be the set of indices of the colors that have representatives. For each color $i\in T$ there is a distinct vertex in $R$ with degree at least $\delta+\mu_i$. Thus we may increase the edge count of $G$ as follows: \begin{equation}\label{lb} \frac{n\delta+\sum_{i\in[h]}\mu_i+\sum_{i\in T}\mu_i}{2}\le |E(G)|. \end{equation} We let $\{f^\downarrow_i\}$ denote the sequence $\{f_i\}_{i\in[h]}$ sorted in nonincreasing order. Since $f_i\le 2(h-i)+1$, we conclude that $f^\downarrow_i\le 2(h-i)+1$. Because there is no system of distinct representatives of size $t+1$, the sequence $\{f^\downarrow_i\}$ cannot majorize the sequence $\{t+1,t,t-1,\ldots,1\}$. Hence there is a smallest value $p\in[t+1]$ such that $f^\downarrow_p\le t+1-p$. Therefore, the maximum value of $\sum_{i=1}^{h}f^\downarrow_i$ is bounded by the sum of the sequence $\{2h-1,2h-3,\ldots,2(h-p)+3,t+1-p,\ldots,t+1-p\}$. Summing we attain $$\sum_{i\in [h]}f_i\le (p-1)(2h-p+1)+(h-p+1)(t+1-p).$$ Over $p$, this value is maximized when $p=t+1$, yielding $\sum_{i\in[h]}f_i\le t(2h-t)$. Since $h\le \delta-1$, we then have $\sum_{i\in[h]}f_i\le 2(\delta-1)t-t^2$. We now combine bounds~\eqref{ub} and~\eqref{lb}: $$\frac{n\delta+\sum_{i\in[h]}\mu_i+\sum_{i\in T}\mu_i}{2} \le (k-h)(2\delta-2)+\sum_{i=1}^{h} (2\delta+\mu_i+f_i-1).$$ \noindent Hence, since $k \leq \delta-1$, \begin{align*} \frac{n\delta}{2} &\le (2\delta-1)(\delta-1)+\frac{1}{2}\sum_{[h]\setminus T}\mu_i + \sum_{i\in[h]}f_i\\ &\le (2\delta-1)(\delta-1)+(\delta-1-t)(\delta-3/2)+2(\delta-1)t-t^2\\ &\le 3\delta^2-\frac{11}{2}\delta+\frac{5}{2}+\left(\delta-\frac{1}{2}\right)t-t^2. \end{align*} \noindent This bound is maximized when $t=(\delta-\frac{1}{2})/2$. Thus $$n \le \frac{13}{2}\delta-\frac{23}{2}+\frac{41}{8\delta},$$ contradicting our choice for the order of $G$. %\begin{proof}[Sketch of Proof of Theorem~\ref{trianglefree}] %When $G$ is triangle-free, Lemma~\ref{maxdeg} can be improved. %In particular, $\Delta(G)\le 2\delta-2$ since there is at most one edge joining a vertex of maximum degree to each edge in a matching of size $\delta-1$. %Since $\Delta(G)$ is used to bound the value of $\mu_i$ in the proof of Theorem~\ref{main}, the same argument yields the following inequality: %\begin{align*} %\frac{n\delta}{2} &\le %(2\delta-1)(\delta-1)+\frac{1}{2}\sum_{[h]\setminus T}\mu_i + \sum_{i\in[h]}f_i\\ %&\le (2\delta-1)(\delta-1)+\frac{1}{2}(\delta-1-t)(\delta-2)+2(\delta-1)t-t^2\\ %&\le \frac{5}{2}\delta^2-\frac{9}{2}\delta+2+\left(\frac{3}{2}\delta-1\right)t-t^2. %\end{align*} %This upper bound is maximized when $t=(\frac{3}{2}\delta-1)/2$, yielding %$$n\le \frac{49}{8}\delta-\frac{21}{2}+\frac{9}{2\delta}.$$ %\end{proof} It remains to show that this proof provides the framework of a $O(\delta(G)|V(G)|^2)$-time algorithm that generates a rainbow matching of size $\delta(G)$ in a properly edge-colored graph $G$ of order at least $\frac{13}{2}\delta-\frac{23}{2}+\frac{41}{8\delta}$. Given such a $G$, we create a sequence of graphs $\{G_i\}$ as follows, letting $G=G_0$, $\delta=\delta(G)$, and $n=|V(G)|$. First, determine $\delta(G_i)$, $\Delta(G_i)$, and the maximum size of a color class in $G_i$; this process takes $O(n^2)$-time. If $\Delta(G_i)\le 3\delta(G_i)-3$ and the maximum color class has at most $2\delta(G_i)-2$ edges, then terminate the sequence and set $G_i=G'$. If $\Delta(G_i)>3\delta(G_i)-3$, then delete a vertex $v$ of maximum degree and then process the edges of $G_i-v$, iteratively deleting those with two endpoints of degree at least $\delta(G_i)$; the resulting graph is $G_{i+1}$. If $\Delta(G_i)\le 3\delta(G_i)-3$ but a maximum color class $C$ has at least $2\delta(G_i)-1$ edges, then delete $C$ and then process the edges of $G_i-C$, iteratively deleting those with two endpoints of degree at least $\delta(G_i)$; the resulting graph is $G_{i+1}$. Note that $\delta(G_{i+1}) = \delta(G_i)-1$. If this process generates $G_{\delta}$, we set $G'=G_\delta$ and terminate. Generating the sequence $\{G_i\}$ consists of at most $\delta$ steps, each taking $O(n^2)$-time. Given that $G'=G_i$, the algorithm from the proof of Theorem~\ref{theorem:algorithmic} takes $O(\delta n^2)$-time to generate a matching of size $\delta-i$ in $G'$. The preprocessing step and the process of determining a smallest color class and choosing an edge in that class whose endpoints have minimum degree sum both take $O(n^2)$-time. This process is repeated at most $\delta$ times. A matching of size $\delta-(i+1)$ in $G_{i+1}$ is easily extended in $G_i$ to a matching of size $\delta-i$ using the vertex of maximum degree or maximum color class. The process of extending the matching takes $O(\delta)$-time. Thus the total run-time of the algorithm generating the rainbow matching of size $\delta$ in $G$ is $O(\delta n^2)$.\qed\\ It is worth noting that the analysis of the greedy algorithm used in the proof of Theorem~\ref{theorem:algorithmic} could be improved. In particular, the bound $c_{i+1}\ge c_i-2$ is sharp only if at step $i$ there are an equal number of edges of color $i$ and $i+1$ and both endpoints of $e_i$ are incident to edges with color $i+1$. However, since one of the endpoints of $e_i$ has degree at most $\delta$, at most $\delta-1$ color classes can lose two edges in step $i$. Since the maximum size of a color class in $G$ is at most $2\delta-2$, if $G$ has order at least $6\delta$, then there are at least $3\delta/2$ color classes. Thus, for small values of $i$, the bound $c_i\le 2(k-i+1)$ can likely be improved. However, we doubt that such analysis of this algorithm can be improved to yield a bound on $|V(G)|$ better than $6\delta$. \begin{thebibliography}{9} \frenchspacing \bibitem{BR} R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge University Press, Cambridge, UK, 1991. \bibitem{Die} R.~Diestel, Graph Theory, Springer-Verlag New York (1997). \bibitem{Dir} G.~A.~Dirac, Some theorems on abstract graphs, \textit{Proc. London Math. Soc.} (3) \textbf{2} (1952), 69–81. \bibitem{IRT} A. Itai, M. Rodeh, and S. Tanimoto, Some matching problems for bipartite graphs, \textit{J. Assoc. Comput. Mach.} \textbf{25} (1978), no. 4, 517-525. \bibitem{KY} A. Kostochka and M. Yancey, Large rainbow matchings in edge-colored graphs, In Preparation. \bibitem{KL} M. Kano and X. Li, Monochromatic and heterochromatic subgraphs in edge-colored graphs -- a survey, \textit{Graphs Comb.} \textbf{24} (2008), 237-263. \bibitem{LP} V. B. Le and F. Pfender, Complexity results for rainbow matchings, In Preparation. \bibitem{LSWW} T. D. LeSaulnier, C. Stocker, P. S. Wenger, and D. B. West, Rainbow matching in edge-colored graphs, {\it Electron. J. Combin.} 17 (2010), Note \#N26. \bibitem{Ryser} H. J. Ryser, Neuere Probleme der Kombinatorik, in ``Vortr$\ddot{\text{a}}$ge $\ddot{\text{u}}$ber Kombinatorik Oberwolfach'', Mathematisches Forschungsinstitut Oberwolfach, July 1967, 24-29. \bibitem{Stein} S. K. Stein, Transversals of Latin squares and their generalizations, {\it Pacific J. Math.} \textbf{59} (1975), no. 2, 567-575. \bibitem{Wang} G. Wang, Rainbow matchings in properly edge colored graphs, {\it Electron. J. Combin.} 18 (2011), Paper \#P162. \bibitem{WL} G. Wang and H. Li, Heterochromatic matchings in edge-colored graphs, {\it Electron. J. Combin.} 15 (2008), Paper \#R138. \bibitem{WZL} G. Wang, J. Zhang, and G. Liu, Existence of rainbow matchings in properly edge-colored graphs, {\it Front. Math. China} \textbf{7} (2012), no. 3, 543-550. \bibitem{W} I.M. Wanless, Transversals in Latin squares: a survey, \textit{Surveys in Combinatorics 2011}, London Math. Soc. (2011). \end{thebibliography} \end{document}