Flows and Connectivity · Matchings in Bipartite Graphs

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Problem. Consider the following bipartite graph \(G(U \sqcup V, E)\): \(U=V=[100]\), \[E=\{\{i, j\} \colon 2 \le \operatorname{GCD}(i, j) \le 5\}.\] What is the size of the maximum matching in this graph?

5 points