Appendixfor: Don't RolltheDice, AskTwice: TheTwo-Query DistortionofMatchingProblemsandBeyond

For the statement of the theorem,k Nisaconstant, and we assume that for every graphGamatching extendingk-familyF(G)isspecified.