Testing equality of two multivariate distributions is a classical problem for which many non-parametric tests have been proposed over the years. Most of the popular two-sample tests, which are asymptotically distribution-free, are based either on geometric graphs constructed using inter-point distances between the observations (multivariate generalizations of the Wald-Wolfowitz's runs test) or on multivariate data-depth (generalizations of the Mann-Whitney rank test). This paper introduces a general notion of distribution-free graph-based two-sample tests, and provides a unified framework for analyzing and comparing their asymptotic properties. The asymptotic (Pitman) efficiency of a general graph-based test is derived, which include tests based on geometric graphs, such as the Friedman-Rafsky test (1979), the test based on the $K$-nearest neighbor graph, the cross-match test (2005), the generalized edge-count test (2017), as well as tests based on multivariate depth functions (the Liu-Singh rank sum statistic (1993)). The results show how the combinatorial properties of the underlying graph effect the performance of the associated two-sample test, and can be used to validate and decide which tests to use in practice. Applications of the results are illustrated both on synthetic and real datasets.