This particular graph theory problem is an old chestnut (houses and utilities). The (non-)solution can be found here.