So, I'm able to formulate both linear programming problems like this:
I have a graph G ={V,E}.
Minimum Vertex Cover:
$$ min \sum_{v \in V} x_v\\ x_{v_i} + x_{v_j} \geq 1, (\forall e = (v_i, v_j) \in E)\\ x_v \in \left\{0;1\right\} $$
where $x_{v_i} = 1$ when the vertex $v_i$ belongs to the cover and otherwise.
Maximum matching:
$$ max \sum_{e \in E} x_e\\ \forall v \in V: \sum_{e \sim v}x_e \leq 1\\ \forall e \in E: x_e \in \{0;1\} $$
where $v \sim e$ means incidence of the vertex $v$ and the edge $e$ and $x_e = 1$ when the edge $e$ belong to the maximum matching and otherwise.
But how can I show, that these two are dual problems?
