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.
Hall's marriage theorem has a necessary and sufficient condition for a bipartite graph to have a perfect matching. The existence of at least one perfect matching means there is an optimal perfect matching (one with the sum of weights is maximal) assuming X and Y are finite vertex sets.
see: https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem