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 are, 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 isolated, 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 induced 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.