Here's a geometric graph puzzle for you. Start with the graph of the truncated icosahedron, with 60 vertices and 90 edges. Delete a matching (a set of edges that do not touch each other) consisting only of edges that belong to pentagons in the truncated icosahedron, in order to maximize the number of connected components of the remaining graph. How many components can you make?




Comments:

None:
2013-02-07T20:07:27Z

I got 12 connected components. This is optimal. Is there any particular reason you are asking this question? Is there some geometry involved? In my understanding it is a purely combinatorial problem.

André

11011110:
2013-02-07T21:10:28Z

You can get 12 components by cutting all the edges that do not belong to pentagons, but this is not allowed in the problem as I stated it. I don't think 12 is possible.

As for why: because you can do it physically with these things.

None:
2013-02-08T08:29:43Z

I see, I completely missed the second constraint that you are only allowed to remove edges from pentagons. I think I have the solution for the original question now.

André

None:
2013-02-07T20:25:03Z

Hi David,

I just thought that you maybe dont want to see the answer of your question posted in the comment section. In this case, feel free to delete my comment.

André

11011110:
2013-02-07T21:11:28Z
By default (because you are not a logged-in LJ user) it came in as screened, meaning visible to me but not to others. I unscreened it, though, because I am not convinced it is correct and I couldn't reply with it still screened.
None:
2013-02-08T22:08:05Z
I'm sure it's possible to do better than three.
11011110:
2013-02-08T22:15:07Z
Yes, you can do much better than that.