前言：
本文原为回答知乎上的问题：如何证明SSCG(3)>TREE(3)，特转载于此。
关于SSCG(3)大于TREE(3)的说法来自于 Adam P Goucher 的这两篇博客：Graph minors 和ast Growing Functions Revisited。因为这只是两篇博客，而不是正式证明，所以目前没有严格的关于“SSCG(3)>TREE(3)”的证明。
我研读了他的这两篇博客，自认理解了其中80%的内容，并且我认为其内容是正确的。以下是我关于Goucher的证明思路的解说，如有差错请自行鉴别，也欢迎在评论区提出。
首先，我假定你已经熟悉了TREE(3)的定义，并且知道其为什么是有限的。如果还不清楚，可以看以下一些文章：
貌似无限的有限——良拟序(well quasi orders)关系
并且我也假定你知道一些简单的图论术语，比如点的度数、简单图、平面图等。
那么大家现在应该知道TREE(n)的定义可以从一个“画树”游戏中引出，SSCG(n)的定义可以从一个“画图”游戏中引出，这里的“图”是图论里的“图”。
首先，SSCG游戏中可以画的图都是simple subcubic graph，其定义是：
没有回环边，两个顶点之间最多一条边。（这就是简单图，Simple Graph的定义，）
每个点的度数最多是3，可以有度数为0的点，可以不连通。
SSCG(n)游戏，是一个画一系列图的游戏，游戏规则是：
第i个图最多有i+n个点。
前面的图不能同胚嵌入（Homeomorphism Embeddable）后面的图，或者说前面的图不能是后面的图的小图（minor）。
如此能画出的最多的图的数量就是SSCG(n)。
这里需要介绍一下“小图”（minor）的概念。“小图”的官方译名是“子式”，但我发现这个译名听上去很难受。在本文中，我用“小图”这个译名，因为在这个游戏中，minor确实起到了比较两个图之间“大小”关系的一个作用。
先说明一下“小图”的定义，“小图”是一个二元关系，当图B可以用以下方法转化为图A时，称图A是图B的一个小图：
边收缩：删除某条边，合并其两个顶点为一个顶点，该顶点与原先这两个顶点连接的点都相邻。
删除边（不言自明）；
删除孤立顶点（不言自明）；
以下是一个来自维基百科的小图的例子：
小图关系是图论中非常有用的概念，著名的瓦格纳定理（Wagner's theorem）说：
一个图是平面图（可以画在平面上，且所有边不交叉）当且仅当 和 不是它的小图：
再说明一下同胚嵌入的定义，它也是一个二元关系。当图A可以用“细分”转化为图B时，或者图B可以通过“平滑”转化为图A时，则称图A可以同胚嵌入图B。细分和平滑的定义如下：
找到一个2度的点，删除该点，连接剩下的两条边，就是“平滑”，其逆操作为“细分”。比如：
（图片来自维基百科）
中间的图就是两边的图的同胚嵌入。可以看出，同胚嵌入都是小图（因为使用两次“边收缩”就是“平滑”操作），而小图不一定是同胚嵌入。
这里可以看出同胚嵌入和小图的区别还是比较明显的，小图的条件明显宽松许多。而网上各处所使用标准不一，维基百科上用“同胚嵌入”，但其他多数文章使用“小图”。本人认为小图的概念更清晰和简洁，且采用同胚嵌入规则的话，SSCG(1)游戏的玩法说不通，因此以下我主要使用“小图”这个术语。
比如，对下图：
其所有的小图是：
空集
显然，小图关系具有传递性，但也存在两个图之间，互不为对方的小图，所以小图关系是一个拟序关系（quasi order)。
有一个强大的Robertson-Seymour定理，证明了SSCG图之间的小图关系是一个良拟序（well-quasi order），这意味着不存在无穷递降和无穷不可比的小图序列，也就等于证明了SSCG(n)是有限的。而证明TREE(n)有限的“克鲁斯卡尔树定理”（Kruskal Tree Theorem）是这个定理的一个特例。
也正因为“小图”关系是一个良拟序，以下我也会直接用“大”或“小”，来表示这个关系。比如，图A是图B的拓扑小图，就称：图A比较小，图B比较大。
可以看出，SSCG的游戏规则简直与TREE游戏一模一样，不同点在于树改成了图。SSCG中，也不再有颜色概念，SSCG(n)中的n只是用来确定第一张图的顶点数量。
不妨先试试从n最小的情况玩一下这个游戏，加深理解。
SSCG(0)：
第一张图只能有一个顶点:
第二张图：因为任何两个点的图都比一个点大，所以这里只能是空集 。
所以SSCG(0)=2。
SSCG(1)：
最佳玩法是如下序列 （注意，第一张图可以有两个点了）：
所以SSCG(0)=5。
SSCG(2)：
SSCG(0)和SSCG(1)都平淡无奇，但是SSCG(2)爆发了，其大小至少达到 。
根据Adam P Goucher，SSCG(2)最佳玩法是这样的，Index指的是步数：
其中的 + n(数字) 的意思就是重复后面的图n份，并且是离散的。比如：
就是：
请自行验证，前面的图都不是后面的图的小图（还是挺容易判断的）。
可以看出，虽然SSCG(2)挺大，比TREE(3)还是小很多。它之所以不够大是因为它只能在第一步出现一个三角形，从第3步开始就变成线段和点的游戏了。
SSCG(3)
现在我们来证明SSCG(3)>TREE(3)。一个直接的想法是，把TREE直接当做一张图。但是SSCG(n)要求每个节点度数不超过3，而TREE游戏中，肯定有许多节点的度数大于3，所以不能直接转化。
这里，Adam P Goucher想出了一个方法，可以把每个TREE游戏中的树转化为特定的SSCG图，并且保持TREE游戏的嵌入关系到SSCG中的小图关系。其要点是，把树的每个节点转化成如下的一个环路形状：
其中Child是子节点意思，Parent是父节点意思
其中的Label指的是TREE游戏中的结点颜色，可以用节点数目作为label，来表示不同的颜色。比如，下图是著名的一个TREE(3)游戏开始几步的示意图：
（图片来自维基百科）
图中我们规定三种颜色的大小顺序是：蓝色<红色<绿色，以下我们尝试把前3棵树按以上规则转换为SSCG图。
对第一个绿色的根节点树，它没有子节点，没有父节点。因为其为绿色，为最“大”颜色， 所以用三个节点表示：
对这棵树：
其转换为SSCG图就是:
再下一棵树：
因为规定了蓝色<红色，也就是蓝色可以“嵌入”红色，而红色不可以嵌入蓝色，且之前用了两个节点表示红色的label，那么就可以用一个节点表示蓝色的label。
其转换为SSCG图就是：
至此，我们有了一个规则，可以把TREE游戏中的树转化成SSCG游戏中的图，这种转化有如下特点：
不同的树转化成不同的图。
如果两棵树存在嵌入关系，则转换后的图同样存在小图关系。
如果两棵树不存在嵌入关系，则转换后的图同样不存在小图关系。
如此，我们几乎已经证明TREE游戏可以“嵌入”SSCG游戏，也就几乎证明了TREE(3）< SSCG(3)，但还欠缺几个细节。
首先是，在转换规则中，每个树节点会转换成SSCG中的 个点，其中 是孩子数量， 是label所需节点数量。
由于TREE游戏允许每一步增加一个节点，相当于SSCG游戏中会增加最多7个点。而SSCG游戏每步只允许增加一个点。所以，必须有个办法，在两个转换后的SSCG图中之间插入合适的图，确保游戏可以持续。
Goucher想出的办法是对每棵树增加如下一个计数器(counter)结构：
其中的counter是一系列点，从7个点减少到1个点，确保前面的图不会比后面的小。所以，TREE游戏中的每颗树，理论上会最多会转化成SSCG中的7个图，其形状就是之前的转换规则，再连接以上的counter结构。
另外一个细节是“启动序列”。我们必须证明，可以在SSCG(3)游戏中，玩出足够的步数，可以容纳TREE(3)游戏的开始时的节点。比如根据以上规则，TREE(3)的第一个节点其实转换成了一个23（9 + counter结构中的14个点）个点的图。那么我们就需要证明SSCG(3)至少可以玩到画23个点那步。
这还是比较容易的，以下是Goucher认为的最优的，SSCG(3)的开始几步的玩法：
这些图都不能嵌入TREE游戏中转化后的图，而且很快节点数也会突破23(考虑到SSCG(2)就已经非常大了)。所以，TREE(3)游戏的每一步都有足够空间插入到SSCG(3)中。至此，我们已经（不严格地）证明了SSCG(3)>TREE(3)。
让我们继续挑战自我，来证明SSCG(3)>TREE(TREE(TREE(TREE(TREE(...TREE(3)...)))=，TREE(3)重嵌套的TREE(3)。
实际上，我们要证明更强的结论：
即重嵌套的。
此时我们证明TREE(3)游戏能嵌入SSCG(3)已经不够了，我们必须要认真地“玩”一下SSCG(3)，使得在其过程中，可以插入茫茫多个TREE(3)“小游戏”。
上文已经提到，SSCG(3)的开始几步可以这样玩：
以上玩到第17步，接下去我们按如下策略玩：
首先定义4个形状，因其形状类似有机化学分子，名称都借用有机化学中的名词来构造（这是原作者的想法）：
反式-二甲基乙烯（trans-dimethylethene）：
顺-二甲基乙烯 （cis-dimethylethene）：
甲基乙烯（methylethene）：
乙烯（ethene）：
以上这些形状的特点是（用序号指代这些形状）：
1）1号和2号互不为小图。
2）3号是1号和2号的小图，4号是1到3号的小图。
3）游戏前17步都不是1到4号的小图
4）1到4号都不是所有TREE游戏中转换后的图的小图。
从第18步开始，所有的图都是如下几个部分的离散组合：
p个反式-二甲基乙烯
q个顺-二甲基乙烯
r个甲基乙烯
s个乙烯
某个图T，且乙烯不是T的小图
用这个五元组来表示某一步的图：，
比如第17步：
可以记作。
如果某一步是，将其下一步记作，称为“后继图”，则以下五个条件中，至少有一个成立：
且
且
且
且T不是T'的小图。
有了以上记号和后继图性质，我们可以方便地继续书写游戏。Goucher认为第18步是如下这个图（Gn表示第n步，下同）：
G18:
15-cycle是指15个点组成的环路，那么这张图就是一个“反式-二甲基乙烯”加15-cycle构成的SSCG图。可以验证，前面17张图不是这张图的小图。
但对这步我有一个疑点。“反式-二甲基乙烯”图有8个点，15-cycle有15个点，一共是23个点。而在第18步，最多只能出现18+3=21个点。所以，这里似乎应该改成13-cycle或者推迟到第20步。但这样最多只对SSCG(3)的数值减少2，是无足轻重的（“无足轻重”前应该加入TREE(3)个“绝对”）。
以下快进到第一阶段的玩法：
G19：
...
G29：
G30：
G31：
G32：
...
G()：
G()：
其中H1、H2、H3就是SSCG(2)游戏开始的三张图。可以看出，第一阶段就是在T的位置上玩了一整个SSCG(2)，来到第步，留下一个“反式-二甲基乙烯”图。
第二阶段游戏开始精彩起来，到这个阶段，“反式-二甲基乙烯”不能再出现了，但我们可以加入非常多的“顺-二甲基乙烯”。
如果用T1表示，按之前规则转换后的，TREE(3)游戏最佳玩法的第一张图，那么下一步就是：
第G()步：
接下来就是在T的位置上，玩一个完整的TREE(3)游戏，直到T变成空集：
第G()步：
大老李注：
这里我有一点不解的是，作者Goucher认为TREE(3)的每一张图可以转换为SSCG里的张图，其中是label数量。通过上半部分的阐述中，我能理解因为Counte结构的存在，每张TREE游戏的图可以转化为7张SSCG里的图，但我不理解这里为什么可以加入。这里的是常量3还是与每张TREE图的形状相关？
我暂认为Goucher是正确的，而且加入或者去掉那个对最终结论影响不大。
接下来，
第G()步：
其中的U1就是游戏的第一步，经过转换后的图。（这张图的点数很少，所以，可以看到有没有区别不大，这步浪费的点数是很多的）
后面的玩法大家应该能猜到了，经过步：
下一步是：
其中的是的第一步。
那么经过步，到达：
那么可以推知，至少再经过步（！），游戏到达：
至此，我们已经证明了：
并且游戏还远没有结束！
