1
$\begingroup$

A matching $M$ in a undirected graph $G(V,E)$ is a subset of the edges of $E$ such that no two edges in $M$ are incident to a common vertex.

A perfect matching ${M}'$ is one in which every vertex is matched.

Example Image

So I want to express the set ${M}'$ with a mathematical-logic notation.

Here is my try:

${M}' = \{ (u,v) \in E : \forall u \in \! V \; \; \exists ! (u,v) \in E\}$

Is it correct? If it is correct, and someone has a - better or more formal - solution, please write it!

$\endgroup$

1 Answer 1

1
$\begingroup$

Your answer is correct. For any vertex there is one (and only one) edge in the matching.

I don't know what you mean by better or more formal, your definition is already formal ...

However an other way to define it is: $$(\forall x, \exists y, E(x,y)\wedge M(x,y) )\wedge (\forall x,\forall y,\forall z, (M(x,y)\wedge M(x,z) \implies y=z) $$

$\endgroup$

You must log in to answer this question.

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