MathCastle
Graph TheoryEasyBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Easy problem

Six people 1,2,…,61,2,\dots,6 are friends as follows: 1,2,31,2,3 are mutual friends (every pair of them is a friendship), and in addition 33 and 44 are friends, 44 and 55 are friends, and 55 and 66 are friends. What is the maximum number of disjoint friend-pairs that can be matched up for a project, each person joining at most one pair?