October 1999
<<September October November>>
| 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). |
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com