# inadmissible bipartite graph

Consider the optimal perfect matching problem on a bipartite graph G= (X $$\cup$$ Y, E) with $$\vert X \vert = \vert Y \vert$$ and a weight function $$w: E \to \mathbb{R}$$. We want to find a perfect matching with maximal sum of edge weights. Where all edges in E are between X and Y only. Is there a canonical example of a bipartite graph that does NOT have a perfect matching? (so called inadmissible bipartite graphs).

Certainly we can isolate a vertex from X or Y and get inadmissibility. Can a fully connected bipartite graph be inadmissible? (these are the graphs I am working with)

Recall a perfect matching M is defined as a subset of E such that each node in X is incident to precisely one edge in M and each node in Y is incident to precisely one edge in M.

• okay, maybe this is obvious: fully connected bipartite graphs always have an optimal perfect matching since there is always atleast one perfect matching? Oct 24 '18 at 1:49
• see Hall's marriage theorem: en.wikipedia.org/wiki/Hall%27s_marriage_theorem Oct 24 '18 at 1:57