Exercise $3.$ This exercise examines maximum edge matching in a non$-$bipartite graph, and illustrates that it is possible to add new constraints that preserve the optimal integer solution but improve the agreement between the optimal real solution to the LP relaxation and the optimal integer solution.

Consider the following "envelope graph" $G$ with vertex set $V(G),$ edge set $E(G),$ with edge weights $c(e)$ for einE$(G)$ as indicated

The associated integer program is

$mamize{\displaystyle \underset{\text{e}\text{i}\text{n}\text{E}(G)}{\overset{?}{}}}c(e)x_e$

subject to

${\displaystyle \underset{?}{\overset{?}{}}}$