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$?



Matching number and chromatic number
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.


