下面这个趣题出自 Using your Head is Permitted 谜题站 2016 年 8 月的题目，稍有改动。
屋子里有若干个人，任意两个人都有恰好 1 个共同的朋友。这有可能吗？有可能。比方说，屋子里有 9 个人，其中 8 个人正好组成 4 对朋友，第 9 个人则和前面 8 个人都是朋友。容易验证，任意两个人都有恰好 1 个共同的朋友。我们可以用下面这个图表示此时这 9 个人之间的朋友关系，其中每个点代表一个人，如果两个人是朋友，就在他们之间连一条线。
除了上图展示的情况之外，我们还能构造出很多别的同样满足要求的情况。事实上，上述方案可以扩展到一切奇数个人的情况，比如下面这样：
著名的四色定理（four color theorem）告诉我们，如果一个地图由若干个连通区域构成（没有飞地），那么在给每个区域染色时，为了让相邻区域的颜色不同，最多只需要四种颜色就足够了。不过，这个结论成立有一个条件：整个地图已经事先确定了。如果我们每次只增加一个区域的话呢？具体地说，如果每次你给一个区域染色之后，我再画出下一个区域，并且之前已经染好颜色的区域不能再修改了，那么四种颜色还足够吗？这里，我们假设，在染色时，你总是遵循一个非常朴素的贪心策略：用第一个合法的颜色给每个新的区域染色。下面这个例子告诉我们，在这些假设下，四种颜色就不够了，有时五种颜色是必需的。
我们的问题就是，在这些假设下，五种颜色就一定够吗？有没有可能构造出某个情况，使得六种颜色是必需的？有没有可能构造出某个情况，使得七种颜色是必需的？
若干个顶点（vertex）以及某些顶点对之间的边（edge）就构成了一个图（graph）。如果图 G 和图 H 的顶点数相同，并且它们的顶点之间存在着某种对应关系，使得图 G 中的两个顶点之间有边，当且仅当图 H 中的两个对应顶点之间有边，我们就说图 G 和图 H 是同构的（isomorphism）。直观地说，两个图是同构的，意思就是它们本质上是同一个图，虽然具体的画法可能不一样。下面的两个图就是同构的。其中一种顶点对应关系是： 1 – a, 2 – c, 3 – d, 4 – b, 5 – e, 6 – g, 7 – h, 8 – f 。
目前，人们还没有找到任何高效的算法，能迅速判断出两个图是否同构。在普通计算机上，判断两个图是否同构，这需要花费大量的时间。因此，人们经常以图的同构为例，来解释复杂度理论和现代密码学中的诸多概念。
假设你家里的计算机十分强大，能很快判断出两个图是否同构，还能在两个图确实同构的情况下，给出一种顶点对应关系。但你的同桌家里的计算机却非常弱，没法做什么大型运算。课堂上，老师向全班展示了两个很复杂的图，不妨把它们叫作图 G 和图 H 。老师布置了一个特别的选做题：判断出这两个图是否同构。每个同学都可以提交答案，答案里只需要写“是”或者“不是”即可。按时提交答案并答对者，期末考试会获得 5 分加分；按时提交答案但答错了的，期末考试成绩将会倒扣 30 分；不参与此活动的同学，期末考试既不加分也不扣分。显然，每个同学都不敢随意提交答案，除非百分之百地能保证自己获得的答案是正确的。回到家后，借助家里的超级计算机，你很快判断出了这两个图是同构的。你给你的同桌发送了信息：“我已经算出来了，这两个图是同构的。”但是，你的同桌却回复说：“你不会是骗我的吧？”你打算怎样说服他，这两个图确实是同构的呢？
下面这道题目是 Using your Head is Permitted 谜题站 2015 年 12 月的题目。
若干个顶点（vertex）以及某些顶点对之间的边（edge）就构成了一个图（graph）。下面就是这篇文章里会用到的四个图。其中，第一个图是由 2 个顶点组成的路径（path），因而我们把它称作 P2 ；第二个图是由 3 个顶点组成的路径，因而我们把它称作 P3 。第三个图是由 3 个顶点组成的一个环（cycle），因而我们把它称作 C3 ；第四个图是由 4 个顶点组成的一个环，因而我们把它称作 C4 。
选取图中的一个或多个顶点，同时选出这些顶点之间的所有边，得到的就是原图的一个“诱导子图”（induced subgraph）。在这篇文章中，我们只考虑那些连通的诱导子图。下面是一个有 6 个顶点的图，右边则列出了由它可以产生出来的所有连通诱导子图。注意，由于有些诱导子图不是连通的（比如只选择正上方的两个点和右下角的两个点，或者干脆只选择最左边那个点和最右边那个点），因而它们并没有在右边列出。在这些连通诱导子图里，很多图的本质都是相同的。比方说，第一行最后三个图和第二行前面四个图的本质是一样的，它们都是刚才我们介绍过的 P2 。当然，第一行的前六个图的本质也都是一样的，即由单个顶点构成的图，有时会被人们记作 K1 。观察最后一行的倒数第二个和倒数第三个图，你能看出这两个图的本质也一样吗？只不过，它们就没有什么固定的名字了。在这些连通诱导子图里，哪一种图出现的次数最多呢？答案就是 P3 ，它一共出现了 8 次。
我们的问题是：能否构造一个图，使得里面出现次数最多的连通诱导子图是 C3 ？能否构造一个图，使得里面出现次数最多的连通诱导子图是 C4 ？注意，如果两种连通诱导子图出现的次数一样多，那它们都不算出现次数最多的连通诱导子图。
若干个顶点以及某些顶点和顶点之间的连线，就构成了一个“图”。如果对某个图进行变换，使得原来任意两个有连线的顶点之间都不再有连线，原来任意两个没有连线的顶点之间现在都有连线了，那么所得到的图就是原来那个图的“补图”。如果一个图和它的补图具有本质上完全相同的结构（这意味着，把其中一个图的顶点以适当的方式与另一个图的顶点建立一一对应的关系，那么对于谁和谁之间有连线、谁和谁之间没有连线这样的问题，两个图的情况是完全一样的），我们就说这个图和它自己是互补的。下图显示了一个顶点数为 5 的图以及它的补图，容易看出，它们的本质结构是相同的。这说明，顶点数为 5 的图有可能和自己互补。
下图显示了一个顶点数为 8 的图，它和它的补图也具有同样的本质结构（你能看出来吗）。这说明，顶点数为 8 的图也有可能和自己互补。
我们今天的问题是：对于那些正整数 n ，存在顶点数为 n 的与自己互补的图？