Covering symmetric supermodular functions with graph edges: A short proof of a theorem of Benczúr and Frank

In this note we give a short and relatively simple algorithmic proof of a theorem of Benczúr and Frank on covering a symmetric crossing supermodular function with a minimum number of graph edges. Our proof method also implies a deficient form of the theorem.