I'm studying Hopcroft-Karp algorithm in bipartite graph.

I can understand the theorems about the algorithm, but I want to find a more specific example.

Can I find a bipartite graph that iterates an algorithm more than three times?

I tried to find it, but most of graphs ended in two iterations. (1 BFS + 1 DFS)

  • mathoverflow.net/questions/268709 is a question in which in the accepted answer I use the algorithm to find maximal intervals which match integers to primes dividing them. Even though the integers are represented by low degree vertices, you might try generating those graphs to see if one of them serves your purpose. By stitching some of these graphs together you might be able to make a large example that does what you want. Gerhard "Make Large Problems From Small" Paseman, 2018.07.12. – Gerhard Paseman Jul 12 at 15:10

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.