Three children inherited 17 camels. The will gave one half to one child, one third to a second child and one ninth to the third. The children did not know what to do and a neighbor offered to lend them a camel. Now there were 18 camels. One child got camels the second got camels, and the third got camels. Altogether they got 17 camels so they could give back the extra camel to the kind neighbor.

In the very short 2003 paper A simple algorithm for edge-coloring bipartite multigraphs, Information Processing Letters 85 (2003), 301-302, Noga Alon used a similar idea for algorithmic purposes. (He also observed the connection to the camel riddle). Here is how the extra camel idea is used for:

**Theorem:** A bipartite cubic graph has a perfect matching.

(A cubic graph is a 3-regular graph.)

**Proof:** Suppose that has vertices. Multiply each edge times ( large) so that the degree of each vertex is of the form . Now ask your neighbor to give you an additional perfect matching and add it to the graph which now is regular of degree . The new graph has an Eulerian cycle. (If not connected, every connected component has an Eulerian cycle.) When we walk on the Eulerian cycle and take either the even edges or the odd edges we get two subraphs of degree . At least one of them does not use all the edges of the neighbor. We move to this subgraph and give the unused edge back to the neighbor. We repeat, and in each step we move to a regular subgraph of degree a smaller power of two, and give back at least one edge to the kind neighbor. If is large enough to start with we will end with a perfect matching that uses only the original edges of our graph.

(Remark: We can take or . If we are a little more careful and in each step try to give many edges back to the kind neighbor we can use or so.)

Of course, it will be interesting if some thing like this can work for finding 3-edge coloring for other classes of cubic graphs which are 3-edge colorable.

In general, UP vs NP is a completely different problem than P vs. NP. In particular, while a strong connection of NP and (promise) UP is already known, P is widely believed to be different than NP. We define a problem that we call General Quadratic Congruences. We show General Quadratic Congruences is an NP-complete problem. Moreover, we prove General Quadratic Congruences is also in UP. In this way, we demonstrate that UP = NP.

https://hal.archives-ouvertes.fr/hal-01304025v6/document

Pingback: Proof By Lice! | Combinatorics and more

Pingback: Giải Thuật Lập Trình · Đẹp 1