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?

• Do you understand the idea of a collection of disjoint pairs? Nov 10, 2015 at 4:29
• 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? Nov 10, 2015 at 4:32
• 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. Nov 10, 2015 at 4:55
• Oh! Maximum is the most number of "disjoint pairs" that can be formed. Cool, thanks hardmath! Nov 10, 2015 at 4:58
• It would make your Question a little bit better to cite (give title and author) the paper where this definition is found. Nov 10, 2015 at 13:41

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.