Finite Playground

To verify is human; to prove, divine.

Perfect matching equivalence

Leave a comment

There are so many things can be written…

Anyway, the following observation is really interesting; details can be found in the book “matching theory” by Lovasz and Plummer.

Consider a general graph G.  An equivalence relationship can be defined on the nodes of the graph as follows: two nodes x and y are equivalent if G-x-y has no perfect matching(!).  


Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s