I know that not all bipartite graphs have perfect matching, but I am having trouble coming up with an example (I'm a visual learner). Can someone give me a visual example of a bi[artite graph without perfect matching?
Does a bipartite graph without perfect matching exist
bipartite-graphsdiscrete optimizationgraph theorymatching-theory
Best Answer
Take a chain graph with 3 vertices and 2 edges:
$$ \bullet - \circ - \bullet $$
If you use the left edge, then you cannot use the right one (because you cannot use the white vertex twice), and similarly if you use the right edge, then you cannot use the left edge. Either way, a black vertex will be left unmatched.