Ponder This Challenge - October 1999 - Path 1 or 2 in directed graph

Ponder This Challenge:

Background and notation:
A "directed graph" consists of a collection of "vertices" {A,B,C,....} and "edges" {(B,C),...}.
An edge goes from one vertex to another: (B,C) goes from the source B to the destination C. There may or may not be another edge from C to B. In the present problem no edge will go from a vertex to itself (loops), nor will two edges have the same source and same destination (multiple edges).
A "path of length two" from B to C is a pair of edges (B,D) and (D,C) where the destination of the first edge is the source of the second.

Our particular directed graph has between 30 and 40 vertices, inclusive. For any two nodes B and C, there is either an edge (B,C) or exactly one path of length two from B to C, but not both.
This is true even if C=B: there is exactly one path of length two from B to B.

The question: How many vertices are in the graph?

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  From each vertex B to each vertex C there is either a one-step path (a single edge) or a unique two-step path. But we'll analyze the problem by looking at three-step paths as well. Fix two vertices B and C. Suppose there are k different vertices H such that (H,C) is an edge. Call these vertices the "predecessors" of C.

  Suppose also that there are m different vertices G such that (B,G) is an edge; call these vertices the "followers" of B. How many paths, of length either two or three (but not one) are there from B to C? First answer: there are m such paths. Each two- or three-step path from B to C consists of an edge from B to some vertex G, followed by the unique one- or two-step path from that vertex G to the destination C.

  Since there are m edges leading out of B, and each can be completed to exactly one path of length 2 or 3 to C, there are m such paths. Second answer: k. Each two- or three-step path from B to C is a one- or two-step path from B to one of C's predecessors H, followed by a one-step path from that vertex to C. Each of the k predecessors of J accounts for exactly one such path. So we must have k=m.

  By the same reasoning, each vertex D has exactly k two- or three-step paths to C, and so has exactly k successors. Similarly we can see that each vertex has exactly k predecessors. (In graph terminology, each vertex has in-degree k and out-degree k.) Now consider one- or two-step paths starting at B. There are exactly k vertices H reachable by a one-step path. Since each of these vertices also has exactly k followers, there are exactly (k*k) vertices reachable from B via two-step paths. This accounts for all the vertices, so the total number of vertices is k+(k*k).

  We know there are thirty to forty vertices, so we must have k=5 and the number of vertices is thirty. It turns out (though this is harder to prove) that the vertices can be given consistent labels of the form Vij, where i and j are two different indices from the set {1,2,...,k+1}, and where an edge goes from Vij to Vkh if and only if j=k.

  Illustrating in a smaller case k=2, we would have 6=2+4 vertices V12, V13, V21, V23, V31, V32, and twelve edges (two coming out of each vertex): (V12,V21), (V12,V23), (V13,V31), (V13,V32), (V21,V12), (V21,V13), (V23,V31), (V23,V32), (V31,V12), (V31,V13), (V32,V21), (V32,V23).

Solvers

• Alamaru Krishal/Krishna (10.1.1999 @ 7:48 PM EST)
• Lawrence T. Hoff (10.1.1999 @ 11:17 PM EST)
• Aleksandar Basaric (10.2.1999 @ 6:13 AM EST)
• Alan Nash (10.2.1999 @ 5:10 PM EST)
• Jimmy Hu (10.4.1999 @ 2:28 AM EST)
• Brett Maune (10.4.1999 @ 10:11 PM EST)
• H.P.Ravikiran (10.8.1999 @ 10:23 AM EST)
• John D. Valois (10.10.1999 @ 11:25 PM EST)
• Mani Aulakh (10.11.1999 @ 5:24 AM EST)
• David Radcliffe (10.12.1999 @ 6:49 PM EST)
• David Morley (10.12.1999 @ 11:14 PM EST)
• msk (10.15.1999 @ 12:04 PM EST)
• "algor" (10.17.1999 @ 1:46 PM EST)
• Meg Meek (10.17.1999 @ 5:14 PM EST)
• Mihai Cioc (10.18.1999 @ 9:46 AM EST)
• Ibrahim Okuyucu (10.21.1999 @ 12:43 PM EST)
• Gundars Kokts (10.26.1999 @ 5:19 PM EST)
• Ming-Wei Wang (10.26.1999 @ 6:16 PM EST)
• Dave Biggar (10.28.1999 @ 10:11 AM EST)
• Surender Baswana (10.28.1999 @ 5:21 AM EST)
• Michael Moyer (10.30.1999 @ 4:43 PM EST)