趣题：随机选取两个无穷大的图，求两者相同的概率

假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？

令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, …给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。

我们先来定义一个东西。我们说一个图是“任意连通”的，如果对于任意两个不相交的有限点集U和V，总能找到一个顶点x，使得x和U里面的所有顶点都相连，但和V里面的任一顶点都不相连。下面我们先证明，随机选取一个无穷大的图，该图满足任意连通性的概率为1；其次我们说明，所有满足任意连通性的图都是同构的。

为什么一个随机选取的无穷大图具有任意连通性的概率为1呢？我可以反过来说明，一个随机图不满足该性质的概率为0。考虑两个任意的有限点集U和V，假设这两个点集一共有n个点。那么，随便选取一个点x，它和U里所有点都相连，但和V里所有点都不相连的概率显然为1/2^n（因为两点之间是否相连是独立确定的，且概率为1/2）。不管n有多大，1/2^n总是一个不为0的数，但供我选的点有无穷多个。在我第k次选点后还找不到满足条件的点的概率为(1-1/2^n)^k，它是一个最终趋于0的值。

然后我们来证明，只要两个图都满足这个性质，我一定能为它们的顶点适当编号，使得图A的点x点y之间有边当且仅当图B的点x点y之间有边。这个证明是构造性的。假设我们已经找到了一个图A和图B的同构子图，这个子图有6个顶点，分别标号为1, 2, 3, 4, 5, 6。在图A当中选取下一个未编号的顶点，把它标号为顶点7。假设顶点7和前面6个顶点中的2, 4相连，和1, 3, 5, 6都不相连。由于图B满足任意连通性，因此图B当中必然也存在一个点，它和自己图里的那个2, 4相连，和1, 3, 5, 6都不相连。于是，把图B中的这个新的点编号为顶点7。不断执行该操作，就可以给图里的每个顶点确定一个适当的编号。

有一个问题是，不断这样操作后，虽然图A里的所有顶点都能找到图B中的对应顶点，但图B中可能还剩有顶点一直未被编号。问题的解决办法也很简单：利用任意连通性找到图B中与图A中的顶点7相对应的点后，立马换成让B选取下一个未编号的顶点并命其为顶点8，让图A利用任意连通性来找它的对应点。如此交替变更图A和图B的角色，就能保证两个图中的每个点都能编上号了。

那么，为什么我刚才说，我们选出的图都和第二段中描述的那个图相同呢？因为，那个图显然满足任意连通性。

来源：http://blogs.warwick.ac.uk/dangoodman/entry/something_completely_ridiculous/