# Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).

For odd integers $n$ we have $n=\chi(K_n) = 2\cdot\mu(K_n) + 1$. Question: is there a non-complete graph $G$ with $\chi(G) = 2\cdot\mu(G) + 1$?

-

Yes there is, but they only differ from the complete graph by adding isolated vertices. The proof goes as follows:

Let $G$ be a graph with $\chi(G) = 2\cdot\mu(G) + 1$ we will show that it is a complete graph plus some isolated vertices. Consider the vertices of a maximal matching: $x_1, x_2, \ldots , x_{2\mu(G)}$. Since it is a maximal matching the other vertices form an independent set. Let us try to color the graph with $2\mu(G) \mbox{}$ colors. Lets color $x_i$ with color $i$. the remaining independent set can be colored without additional color as long as there is no vertex adjacent to all of the $x_i$. As this would be a contradiction we conclude that there is a vertex $\alpha$ outside of the matching which is adjacent to all the $x_i$. As this is a maximal matching, all the other vertices must be independent, otherwise we could make a larger matching.

So far we have a matching of size $\mu(G)$ and $\alpha$ which is adjacent to every vertex in the matching, and all the other vertices are isolated. We only have to show that the graph induces by these $\mu(G)+1$ vertices is complete. This can be done as we can form another matching of the same size by replacing an $x_i$ with $\alpha$, and the same reasoning says that $x_i$ is adjacent to every vertex of the matching, thus this subgraph is complete.

-

We have an odd number of colours. There is an edge between any pair of colours, or else those colours could be combined. So we can easily generate a matching with $\frac{\chi - 1}{2}$ edges. We are given that we cannot add an edge.

Take the colour $C$ not currently involved in any matching. Suppose that some vertex $v \in C$ is not adjacent to every other colour. Then let $v$ be adjacent to some vertex of colour $A$, but not to any vertex of colour $B$. In the initial matching, pair $A$ with $B$, to get a matching of $\frac{\chi -1}{2}$. Now delete the edge between $A$ and $B$ and add the $v$ to $A$ edge and one $B$ to $C$ edge. Now the matching number is too big. Hence $v$ does not exist - every vertex in $C$ is adjacent to a vertex of every other colour. Since $C$ was arbitrary, every vertex is adjacent to a vertex of every other colour.

Now we simply pick a vertex not yet in the matching and not in the colour $C$ and match it with something in $C$ to break the rule. Hence everything not in $C$ is in the matching, so each colour has only one vertex. But $C$ was chosen arbitrarily, so it too has just one member. Hence the graph is complete.

EDIT: another answer just pointed out that isolated vertices can be admitted, which I missed out when I assumed that the vertex $v$ is adjacent to some other vertex (whose colour I called $A$). Apologies.

-