# Prove that this linear relaxation has half-integral extreme points

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?