Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope:
(1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$
(2) For each $e \in E$, $0 \leq x_e \leq 1.$
Here $\delta(S)$ is the set of edges with exactly one endpoint in $S$.
It is known that the above polyhedron has integral extreme points when G is a bipartite graph. It is also known that, in a general graph, any extreme point of the polyhedron is half-integral - that is, it's coordinates are either integers or multiples of 1/2.
I am trying to prove the half-integrality on general graphs by using a transformation to a new bipartite graph $\tilde G$, obtained from $G$ by placing a new vertex 'in the middle' of each edge. Note that this makes $\tilde G$ a bipartite graph.
However, I'm struggling with the details. Given an extreme point of the polytope for $G$, I need to somehow create a feasible point for $\tilde G$. Then I can apply the integrality and transform it back somehow.
Can anyone help me out with how to proceed?
