度不超过3，直径不超过d的无向图最多有几个点？
一个无向图由若干个顶点和连接2个顶点的若干条无向边组成。一个顶点的度就是与该顶点有边相连的点数。很有趣的问题，结果需要巧思，构图很优美。
图的直径就是相距最远的2个顶点的距离。
2个顶点的距离就是从1个顶点出发，按照图中的边走到另1个顶点所经过的最少边数。
如果从1个顶点出发，按照图中的边无法走到另1个顶点，我们就认为这2个顶点的距离是$+\infty$。
问：每个顶点的度都不超过$3$，直径不超过$d$的无向图最多可以有多少个顶点？
例如：
当$d=0$时，最多有$1$个点，这个点的度是$0$。
当$d=1$时，最多有$4$个点，这$4$个点两两相连，每个点的度都恰好是$3$。
那么，对于更大的$d$，答案是多少呢？ d=2时，Vmax=10，为PetersenGraph(5,2)
一个简单的上限
容易给出一个简单的上限。以d=2为例。先给定一个3度点（始点），它发出3条边，指向3个顶点（1 级顶点），其余的顶点必须与 1 级顶点相连。而每个 1 级顶点最多再发出2边条，指向2个顶点（二级顶点），故最多6个二级顶点。所以d=2时，最多10个顶点。
对于更多大的 d, 逐级类推，最多$3*2^d-2$个点。对于d=3，这个上限为22。22个顶点的3度图已经很多了，想用编程搜索的办法来解这个问题，估计走不了多远。 2# hujunhua
我也曾想到五角星，但没想到如此美妙的方案。
3#gxqcn
我最初画出来的图是下面这样的：过程如下：先确定一个3度点为始点（10），然后生成 1 级点（1，2，3）和 2 级点（4~9）。始点和 1 级点都是3度点了，度数已饱和，所以只需要考虑6个二级点构成的二度图（6个 2级点已各有1 边，不在所考虑的子图内）。假定图的连通效率最高，则最短回路的长度必定为5. 所以6个二级点构成的二度图应该是一个长度为6的回路。在这两条的启示下，很容易作出余下的边。
将这种方法推广到d=3的情况，首先得到如下的图，
同样，只有末级点是未饱和点，只需要考虑12个末级点（10~21）构成的二度图。这时再用编程搜索的方法应该可行了。 很遗憾，
$22$个点，
如上图所示固定$21$条边，
枚举另外$12$条边，
躺等一晚上，
枚举完了，
结果是无解。
我现在迷茫了，
答案不是$(3*2^d-2)$，
会是多少呢？
d=3时，Vmax=20
如果包含2度点，易知最多11点，故必须是3-正则图，则由3V=2E知顶点必为偶数。所以最多只可能是20点了。我手工搞出一个20点的方案（老婆召唤吃午饭，没来得及全面检查，貌似没问题）。至于有没有其它更好的方案，我就不知道了。Fans可以从5#的图中去掉2个末级点搜索一下。 去掉$2$个末级点之后枚举剩余的边，
结果可行方案一个接一个地如泉涌般蹦出来，
我只好按下pause键，才能抓住一个放上来：01112222223333333333
10221133332222333333
12023311333333222233
12203333113332332322
21330233331133222323
21332033323311233232
23133302332232113332
23133320323223331123
23313333022323323211
23313232203231231333
32331323230232133213
32331322322033311332
32333132233302323121
32323123312320132333
33232213321331023323
33232313233123202331
33222331313132320233
33233231232313332012
33322332131323233102
33323223133213313220我的程序输出的是距离表，表中的第$i$行第$j$列表示第$i$个顶点与第$j$个顶点的距离。
我们可以看到，整张表有$20$行、$20$列，距离的最大值是$3$，是一个$d=3$、$n=20$的可行解。
因此我们可以相信hujunhua版主所说的【d=3，Vmax=20】属实无误。
8#KeyTo9_Fans
【d=3，Vmax=20】 是否确实，关键在于你在6#的枚举有没有漏洞。8#用Pause键抓住的那个解，我连了一下，还是7#的那个图。难道这个是唯一解？
我有点不相信，我可是手工在纸上试出来的呀，难道是人品大暴发，两刷子就碰到了这个唯一解了？
图的对称性
极限往往与对称性相伴而行，因此考察一下图的对称性或许可得到一些有用的启示。先罗列几个与图的对称性有关的基本概念和定义。
定义1【图的自同构】图G:={V,E}, f是顶点集 V 的一个变换，若 f(E)=E, 则称 f 为图 G 的一个自同构。
性质1【图的自同构群】图G的所有自同构组成的集合构成群，称为图G的自同构群。
定义2【图的对称度】图的自同构群的阶。
定义3【图的对称点】图G={V,E},v1,v2∈V，若存在G的一个自同构f，使得f(v1)=v2, 则称v1,v2是对称的。
定义4【对称阶】顶点集 V 按对称关系所划分的对称类的阶。
例1：G=简单四边形1234. 写出G的自同构群、对称度、对称阶
自同构群H={(1234),(13),(24),(2341),(12)(34),(14)(23),(13)(24),(4123)}
所以简单四边形的对称度为8。显然，简单四边形的顶点集只有一个对称类，故对称阶为4.
从简单四边形的自同构群来看，将图画成正方形就能完全表现其对称性。
例2：PeterGraph(5,2)（即2#图）
这个图有10个顶点，其自同构群凭手工计算已经不容易了，用M9计算的结果表明，其对称度为120.
相对而言，对称阶更容易观察和计算。2#图的顶点集属于全属于一个对称类，故对称阶为10.
5#的第1个图表现了PeterGraph(5,2)的非5阶对称性，可见2#图没有完全表现PeterGraph(5,2)的对称性。
M9计算出来的自同构群揭示了彼得森图的另外2种令人惊异的几何表现（分享容后）。