**Update:** a greedy approach: am = WeightedAdjacencyMatrix[g1]; DeleteDuplicates[am["NonzeroPositions"][[Ordering[-am["NonzeroValues"]]]][[;; ;; 2]], IntersectingQ] >{{4, 5}, {1, 2}, {6, 8}} **Original answer:** ClearAll[f] f = Module[{dm = Array[a, {1, 1} VertexCount[#], 1], constraints1, constraints2, constraints3, objective}, constraints1 = Join @@ Join[Thread[0 <= # <= 1] & /@ dm, Thread[0 <= # <= 1] & /@ Transpose[dm]]; constraints2 = 0 <= Total[{#, Reverse /@ #}, 2] <= 1 & /@ dm; constraints3 = {Total[dm, 2] == #2}; constraints4 = DeleteCases[Thread[Join@@dm ==Join@@(dm Unitize[am])], True]; objective = Total[dm WeightedAdjacencyMatrix[#], 2]; Maximize[{objective, ## & @@ Join[constraints1, constraints2, constraints3, constraints4]}, Join @@ dm, Integers]]&; **Examples:** edges = Property[#, EdgeWeight -> #2] & @@@ Thread[{{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 4 <-> 6, 5 <-> 6, 6 <-> 7, 6 <-> 8, 7 <-> 8}, {3, 2, 1, 6, 5, 4, 1, 3, 2}}]; g1 = Graph[Range[8], edges, EdgeLabels -> "EdgeWeight", VertexLabels -> Placed["Name", Center], VertexSize -> Large, ImageSize -> Large] [![enter image description here][1]][1] f[g1, 3] /. r : Rule[_, 1] :> Style[r, Red, Bold] [![enter image description here][2]][2] HighlightGraph[g1, Style[f[g1, 3][[2]] /. Rule[a[b_, c_], 1] :> UndirectedEdge[b, c], {Red, Thickness[.02]}]] [![enter image description here][3]][3] HighlightGraph[g1, Style[f[g1, 2][[2]] /. Rule[a[b_, c_], 1] :> UndirectedEdge[b, c], {Red, Thickness[.02]}]] [![enter image description here][4]][4] HighlightGraph[g1, Style[f[g1, 4][[2]] /. Rule[a[b_, c_], 1] :> UndirectedEdge[b, c], {Red, Thickness[.02]}]] [![enter image description here][5]][5] [1]: https://i.sstatic.net/INaMJ.png [2]: https://i.sstatic.net/Gx1qd.png [3]: https://i.sstatic.net/jOgbh.png [4]: https://i.sstatic.net/sa8vm.png [5]: https://i.sstatic.net/hoTvF.png