I am having difficulties understanding what an adjacency matching according to the definition given in a paper.

An adjacency matching in an undirected graph G is a collection of disjoint edge pairs in G such that if two edges e and e' are paired, then e and e' share a common endpoint. A maximum adjacency matching is an adjacency matching with the maximum number of edge pairs.

Could anyone explain what an adjacency matching is according to this definition?

  • $\begingroup$ Do you understand the idea of a collection of disjoint pairs? $\endgroup$
    – hardmath
    Nov 10, 2015 at 4:29
  • $\begingroup$ Nope. Had trouble there too. This is what I think though. If we include two edges (as a pair) in the matching, then we can't include either of these edges in any other pair (or matching). Is that right? $\endgroup$ Nov 10, 2015 at 4:32
  • $\begingroup$ Yes, exactly. Now you are only allowed to use edges that are distinct from one another, yet share one endpoint, to make as many "disjoint pairs" as possible. That's a maximum adjacency matching, as defined in your quoted paper. $\endgroup$
    – hardmath
    Nov 10, 2015 at 4:55
  • $\begingroup$ Oh! Maximum is the most number of "disjoint pairs" that can be formed. Cool, thanks hardmath! $\endgroup$ Nov 10, 2015 at 4:58
  • $\begingroup$ It would make your Question a little bit better to cite (give title and author) the paper where this definition is found. $\endgroup$
    – hardmath
    Nov 10, 2015 at 13:41

1 Answer 1


First, an adjacency matching is defined for a simple undirected (finite) graph $G$ to be a disjoint collection of unordered pairs of (distinct) edges which share exactly one endpoint. Therefore an edge of $G$ can belong to at most one such pair in the collection.

Then a maximum adjacency matching is one that has the largest possible number of edge pairs. Finiteness of $G$ guarantees that the maximum number of pairs is attained by some adjacency matching.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .