Logic formalization for Perfect Graph Matching problem

420 Views Asked by At

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!

1

There are 1 best solutions below

0
On BEST ANSWER

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) $$