# How to find mutually exclusive subgraphs from a list a subgraphs to cover all nodes in a graph?

A list of 132 subgraphs (each with 4 nodes) is also available. A given node is available in multiple subgraphs.

How can I find 17 subgraphs that are mutually exclusive (i.e., one node can be present only in one of the 17 subgraphs) and cover all 67 nodes?

Since we have 67 nodes and want 17 mutually exclusive subgraphs (with 4 nodes each), two subgraphs out of 17 will have one common node. That is acceptable.

In fact, we want 16 subgraphs with 4 nodes each and one subgraph with 3 nodes.

SG is the list of subgraphs.

SG=Uncompress["1:eJyNl81SFEEQhEddFRRFEUTxj0VAfgRxQQFFEbhy8hE4EFEnD/\
AIPjhbGTFTOtOVOZeO2cmvs6pju2q6hxd/fl/+rarqajAezu3q+nLw7y+7NX6w2z4s+\
rA6HlJiRRLwGHYJiHf6ER7APrAoGREew4SAOGiIJelBCQ9gayyKJpYk4aKtd4m7/v6eD+\
99+MiITUnAY7lLQLzfj/AAtsWiZER4LEvCRdvuEhP+fpLt0yCyHQTxQfPPfWJET4/\