Algorithms (graphs)

34.2-2 (Cormen, Leiserson, Rivest, and Stein, Introdution to Algorithms, 3rd edition)

Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is nonhamiltonian.

Introduction to the problem
A bipartite graph is a graph whose vertices can be divided into two disjoint sets A and B such that every edge connects a vertex in A to one in B, that is, A and B are each independent sets.

Examples of bipartie graphs:

As we can see, in the upper picture the graph with odd number of vertices is nonhamiltonian. The second one is hamiltonian.

Proof
Let G=(A∣B,E) be a bipartite graph. To be Hamiltonian, a graph G needs to have a Hamilton cycle: that is, one which goes through all the vertices of G. As each edge in G connects a vertex in A with a vertex in B, any cycle alternately passes through a vertex in A then a vertex in B.

There are odd number of vertices, so |A|!= |B|. Suppose, without loss of generality, that |A|>|B| , that is, that there are more vertices in A than in B. Let |A|=m,|B|=n. Suppose G has a Hamilton cycle C.
Let that cycle start at u∈B. After 2n edges have been traversed, we will have arrived back at u again, and all the vertices of B will have been visited. But there will still be m−n vertices in A which have not been visited. Hence G cannot be hamiltonian. 

QED

Thus, there is limited but practical research at Google, blue-sky research at CERN and "the sky is the limit", sometimes useless research in academia.

http://www.youtube.com/watch?v=jJ-IwnnjBy0

A solution to Exercise 35.2-5 in the book "Introduction to algorithms" by Cormen, Leiserson and Rivest.

Suppose that the vertices for an instance of the traveling-salesman problem are
points in the plane and that the cost c(u,v) is the euclidean distance between
points u and v. Show that an optimal tour never crosses itself.

 

If the optimal tour crosses itself then it can be in a manner shown in the attached picture. Thus, there are edges AC and DB (a tour with crossing) instead of AB and DC (optimal tour). The edge AC can be represented as a sequence of edges: AX and XC. The same can be done for edge DB, which can be represented as a sequence of edges: DX and XB. By the triangle inequality, AB < AX + XB (red) and DC < DX + XC (green). In this case, we can show that the optimal tour cannot cross itself, because: AB + DC < AX + XB + DX + XC = (AX + XC) + (DX + XB) = AC + DB. Now, we can generalize the case, and have a cross between more than two consecutive vertices, for example, A'C' and AC, but then we can see from the picture, that we will have to turn back at some point, for example from A to C (instead of going forward), which lengthen the path even more.

Bret Victor

That's really creative: http://worrydream.com/