Problem: Prove that $P_{\text{match}}(G) \cap\left\{x: 1^T x=k\right\}$ is the convex hull of all matchings in $G$ of size exactly $k$.
My attempt: Firstly, we prove that $$\text{conv}\left\{\chi_M: M \text{ matching of size } k\right\} \subset P_{\text{match}}(G) \cap\left\{x: 1^T x=k\right\}$$ It is indeed, $x \in P_{\text{match}}(G)$. On the other hand, $$1^T x = \sum_{M \text{ matching of size } k} \alpha_M \sum_{e \in E} \chi_M(e) = k.$$ Therefore, we attained the above inclusion relation. For the inverse inclusion, there are two hints
- Explain why it suffices to prove the opposite inclusion for the extreme points.
- Let $x$ be a point of $P_{\text {match }}(G) \cap\left\{x: 1^T x=k\right\}$ and assume that the support of $x$ contains two distinct matchings $M$ and $N$. (Note that $M$ and $N$ need not be matchings of size $k$.) Consider the symmetric difference $M \Delta N$ and prove that $x$ cannot be an extreme point.
However, I did not understand the purpose and how to deal with the two above hints.
Explanation for the notation in the problem:
- $\text{conv}$ denotes for the convex hull.
- $\chi_M$ is a binary vector, i.e, $$\chi_M(e) \begin{cases} 1 & \text{ if } e \in M\\ 0 & \text{ if } e \notin M \end{cases}$$
- $P_{\text{match}}(G) = \text{conv}\left\{\chi_M: M \text{ is a matching in } G\right\}$.