# How to solve a specific dining problem with max flow network?

n people named i are invited to a party. They are a(i) years old.
We want to position them on some tables by obeying the following criteria:

• Each guest must sit around a table.
• Each table should have at least 3 guests around.
• The sum of age of each two adjacent guests around a table should be a prime number.

We need to solve it with the least possible number of tables or inform that it is impossible. For example, if we have 10 guests that all of them are 20 years old, then it is impossible to position them without violating the constraints.

It is a problem related to Max Flow Network. I think we should consider guests as vertices and create edges between them if and only if the sum of their edges is prime, but I'm not sure about the rest of the solution. So, how to solve it with Max Flow Network approach?

• Feel free to ask for more information What is your question? Dec 30 '21 at 16:20
• Just so you know, in general graph Hamiltonian cycle problem is $\mathsf{NP}$-hard. Dec 30 '21 at 20:16