Problem C3 from IMO13 shortlist (AoPS link):
Given an undirected graph. You can perform these 2 operations, one at a time:
1. Remove a vertex with odd degree.
2. Double the graph: for each u, create a copy u'; create edge (u', v') if there is edge (u, v); create edge (u, u') for all u.
Prove that there exists a sequence of these 2 operations such that after performing it, the graph will have no edge.
There's this greedy solution that seems to work really well, that is to remove the odd vertex with largest degree until there's no more odd vertices, then double the graph, then do the same over and over again.
It seems to work for all graphs with <= 7 vertices and for random large graphs. Moreover, the number of operations needed doesn't exceed 3N for all graphs I tested on.
Is it possible to prove that it will work for all graphs? And if it does, what is the upper bound of the number of operations?
Thank in advance.
Did you try to write similar greedy algorithms? For example, remove random odd vertex or odd vertex with smallest degree?
I already came up and proved an algorithm that will work for all graphs. Now I just want to know if the algorithm I said in the blog works too.
But it would be easier to prove random algorithm as we would know that we shouldn't use that the vertex we remove has the largest degree.
As I can see from your comment, that is not always true that we can delete vertices in arbitrary order... So we should use our greedy step.
Any graph must have an even number of vertices with odd degrees.
Keep dynamically removing edges from the graph while there exists at least one vertex with odd degree, pick any if there are many choices.
When there is not any, it implies all remaining vertices have even degree, if a node has degree n, it becomes 2n+1, so the operation yields vertices with odd number.
After every doubling, it's definitely possible to delete at least ome vertex, so the algorithm definitely terminates.
No, it doesn't. Consider the graph 1-2-3-4-1. Double it and then it will remove 1, 3, 2, 4 and it becomes the same graph.
I totally misunderstood the problem I assumed you create only edges + extra self edge not new nodes.
Sorry for the confusion.
Nice tags
So it should become:
who, reads, tags, anyway, except, ivan, and, who, read, his, comment.