Is finding whether k different perfect matchings exist in a bipartite graph co-NP?
Yes, cause the problem lies in P. Look at paper Fukuda, Matsui ''Finding All The Perfect Matchings in Bipartite Graphs''