How to construct an ordinary matching from a fractional matching?

Question

Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $.

My question is : does the fractional matching give a matching that we know (of $G$) i.e. with no conflicting edges? I am confused, since there is no criteria for choosing a fraction $f(e) \in [0,1]$, for every $e \in E$. For example, if we have $e_{1}, e_{2} \in E$ such that $v \in e_{1}, e_{2} $ and I assign $f(e_{1})=1/4$ and $f(e_{2})= 1/2$, then $f(e_{1})+f(e_{2})=3/4 \leq 1 $, hence both $e_{1}$ and $e_{2}$ should belong to the fractional matching.

Thank you in advance.

Answer 1

It is not possible to get a maximum matching from any fractional matching by only looking at the values of the fractional matching. Consider the undirected triangle graph with vertices $v_1,v_2,v_3$ and edges $e_1=(v_1,v_2), e_2=(v_1,v_3), e_3=(v_2,v_3)$. If we assign $f(e_1)=f(e_2)=f(e_3)=\frac{1}{2}$, this is a valid fractional matching. However, an actual matching can only contain one of the edges, so we cannot distinguish these edges by their value.

It is of course always possible to obtain a matching from a fractional matching by first selecting all edges with at least a certain fraction and then removing edges such that you end up with a matching. This matching, however, is usually not a maximum matching.