# Maximum weight perfect matching in general graphs

Let $$G(V,E)$$ be a graph (not necessarily bipartite), where edge $$e \in E$$ has weight $$w_e$$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows $$\text{maximize}~~\sum_{e\in E} w_e x_e \\ \text{subject to}~~\sum_{e\in E: v\in e}x_e=1\text{ for all }v\in V \\ 0\le x_{e}\le 1\text{ for }e\in E.$$ In the corresponding Integer Program $$x_e$$ is a binary variable s.t. $$x_e = \begin{cases} 1 \text{ if } e \text{ is in the perfect matching}\\ 0 \text{ otherwise} \end{cases}$$ I am unable to come up with an example where given $$G$$ has a perfect matching, the LP does not have an all integral optimal solution $$x_e^{\text{*}}$$. I tried taking small examples with odd length cycles, though there was a fractional optimal for the LP, there was an all integral optimal as well (in the examples I took).
I am aware that for bipartite graphs if the LP is feasible, then there always exists an all integral optimal for the LP. Does it hold for general graphs as well? If not I would appreciate hints so I can come up with such an example.

• @Dmitry There is equality because I want perfect matching ie. each vertex should be incident to exactly one edge in the matching. For a triangle, perfect matching does not exist. I want an example of a graph where I know a perfect matching exists and the LP relaxation does not have an all integral optimal Mar 13 at 20:40

Consider the graph consisting of two triangles $$123,456$$ connected by an edge $$34$$. The graph has a unique perfect matching $$12,34,56$$. Give the edges of the triangles weight $$1$$, and the edge $$34$$ weight $$\epsilon$$. The maximum weight perfect matching has weight $$2+\epsilon$$. Conversely, the fractional matching giving a weight of $$1/2$$ to each edge of each triangle has weight $$3$$. Assigning $$x_e = 0.5$$ to all edges except CD gives the optimal LP solution.