1
$\begingroup$

Let $G$ be a $2k$-regular tripartite graph with $V(G)=X_1\bigcup X_2 \bigcup X_3$, and let $|X_i|=2m+1$ for $i=1,2,3$. What is the minimum number of matchings into which $G$ can be decomposed?

Here is my reasoning:

Let each matching be represented by a color, so the problem simply becomes to find the edge chromatic number $\chi(G)$, that is, the minimum number $n$ for which there is an $n$-coloring of $G$. By Vizing's Theorem, we know that $\Delta(G)\leq \chi(G) \leq \Delta(G)+1$, where $\Delta(G)$ denotes the maximum vertex degree of $G$. Here, $\Delta(G)=2k$. Also, notice that the total number of edges of $G$ is $3k(2m+1)$. If $\chi(G)=\Delta(G)$, then $$ \frac{3k(2m+1)}{2k} = 3(m+\frac{1}{2}) $$ implies that the same color is used on at least $3m+2$ edges. However, $G$ has only $6m+3$ vertices, which means that two of these edges must share one vertex, and thus $G$ does not have proper coloring. It follows that $\chi(G)$ must be equal to $\Delta(G)+1$, and therefore, the minimum number of matchings into which $G$ can be decomposed is $2k+1$.

is this a sound proof?

$\endgroup$
4
  • 1
    $\begingroup$ Deleting a question after an answer has been provided is an abusive behaviour, please refrain from it. $\endgroup$ Commented Apr 20, 2018 at 3:07
  • 1
    $\begingroup$ Vandalizing it is not so good, either, John. Hands off! $\endgroup$ Commented Apr 22, 2018 at 7:21
  • 1
    $\begingroup$ PLEASE STOP VANDALIZING YOUR QUESTION, JOHN! $\endgroup$ Commented Apr 23, 2018 at 12:25
  • 1
    $\begingroup$ What Gerry and Jack said. $\endgroup$ Commented Apr 24, 2018 at 7:32

1 Answer 1

1
$\begingroup$

This is correct.

More generally, and by pretty much the same argument, all regular graphs on an odd number of vertices are Class 2 (that is, $\chi'(G) = \Delta(G)+1$.) In all such graphs, the degree of each vertex is even. If you have a $2k$-regular graph on $2n+1$ vertices, then there are $k(2n+1)$ edges. In a $2k$-color edge coloring, the average size of a color is $\frac{k(2n+1)}{2k} = n + \frac12$, so there must be one color with $n+1$ edges, so one of the $2n+2$ endpoints of those edges must repeat, and the coloring cannot be proper.

Even more generally, a $k$-edge-coloring of a $k$-regular graph is necessarily a $1$-factorization of the graph: a partition of the edge set into $k$ perfect matchings. This is another reason why the number of vertices must be even for such a thing to exist.

(It's possible to rephrase your argument to first show that to cover all the edges of $G$, each of the colors must be a perfect matching, and then notice that there's no perfect matching in a graph on $6m+3$ vertices.)

$\endgroup$

You must log in to answer this question.