Given a bipartite graph with v vertices each side, and initially, all vertices are disconnected i.e., 0 edges were in the graph initially, how to count the number of ways of introducing v+2 or v+3 edges such that no perfect matching exists?
Any help is much appreciated. Counting each such combination seems very hard and I think that would not be the right approach as the total number of ways could be huge. Any help, topics, links, suggestions would be appreciated.