Using Flow graph to find maximum matching

Question

I recently submitted an answer to the following question (homework in algorithms course):

A guy has m shirts, n pants, and p belts. he wants to make the maximum amount of outfits while abiding by these rules:

1. Every item can appear at most in one outfit

2. Not every pant can go with the same shirt (we have n X m boolean matrix representing legal combinations)

3. Not every pant can go with every belt (again we have n X p boolean matrix)

my attempt:

create a bipartite graph where V1 ={ v | v is a pair of shirt and a belt} V2= {v | v is a pant}.
we draw an edge between a vertex v from V1 and vertex u from V2 only if the three make a legal combination.

after constructing the graph we create a source connected to all the vertexes of V1 and a sink connected to all the vertexes of V2 and use Ford-Fulkerson algorithm to find the maximum flow which yields the maximum matching of the graph.

My T.A said this was wrong since it won't give me the correct answer, but didn't explain why. Is he right? if he is, where is the fallacy of my solution? (I'm not looking for a better solution, I have seen a better one already, just want to know if this particular one is correct)

Answer 1

Your TA is correct. Your algorithm is wrong.

Here is a simple counterexample for your algorithm. We have two shirts, two pants and one belt. All combinations are legal.

The bipartite graph has 2 nodes representing two shirt-belt pairs and 2 nodes represent two pants. There is an edge between any shirt-belt pair and any pant.

The maximum-matching of the bipartite graph consists of two matches. However, since there is only one belt, we can make at most one outfit.