abcdef6199's blog

A math problem
By abcdef6199, history, 7 years ago, In English

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.

  • Vote: I like it
  • +41
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Did you try to write similar greedy algorithms? For example, remove random odd vertex or odd vertex with smallest degree?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I totally misunderstood the problem I assumed you create only edges + extra self edge not new nodes.

      Sorry for the confusion.

      → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice tags

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    So it should become:

    who, reads, tags, anyway, except, ivan, and, who, read, his, comment.

    → Reply