On the French wikipedia, one can read:

Soit un graphe simple non orienté $G = ( S, A )$ (où $S$ est l'ensemble des sommets et $A$ l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage $M$ est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que $\forall (a, a') \in M, a \neq a' \Rightarrow a \cap a' = \emptyset$.

which translates to:

Let $G = (S, A)$ be a simple non-oriented graph (where $S$ is the set of vertices and $A$ is the set of edges, which are pairs of vertices), a matching $M$ is a set of pairwise non-adjacent edges. In other words it means that $M$ is a subset of the set $A$ ($M \in \mathcal{P}(A)$) so that, $\forall (a, a') \in M, a \neq a' \Rightarrow a \cap a' = \emptyset$.

I can't understand what does mean $a \cap a' = \emptyset$. Because, to my view, $a$ and $a'$ are two different edges (not two different sets of edges or if it's the case I can't see why it would) how it is possible to apply them the cap operator? And what does it mean?


The authors are identifying an edge with the pair of vertices it is incident to (since the graph is simple this can be done uniquely). This is pretty common in the literature. In fact it is not unusual for edges to be defined as pairs of vertices.

  • $\begingroup$ Indeed, looking it from this way makes sense. Thank you very much you for your help. $\endgroup$ – 永劫回帰 Aug 9 '15 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.