## Interesting Problem in Graph Theory

2012-06-27

One of my homework problem for SYSM6302: Dynamics of Complex Networks and Systems, where we review basics of Graph Theory:

Here is a diagram of a prison for political dissidents. The prisoners have been divided into seven groups as shown. A spy plans to help all the prisoners escape by blowing up the gates in the prison walls. Due to the danger of this plan, he wants to destroy as few gates as possible and still allow all prisoners to escape. How many gates must be blasted to do this?

The answer will be posted next week ;)