转自知乎“寒树”

Ⅰ
子曰：三人行，必有我师焉。

韩愈在写《师说》的时候，便引用了这句话，然后就不加证明地给出“是故弟子不必不如师，师不必贤于弟子”的结论。事实上，我们可以把一些概念抽象，给出数学上的严格证明。

于是，在承认 选择公理 的前提下(当然这是废话)，我们给出如下定义：

定义1：设A₁，A₂，A₃,...,A_n  (n≥3)为平面上n个点，记AiAj(输入法原因，应有上画→，下面记为Ai→Aj)为由Ai指向Aj的有向线段 .对Ai，Aj.当Ai→Aj存在时，称Aj为Ai的“师”.

现在回想孔子那句话，其实我们也无法用现有的理论证明它，于是我们不妨承认它为公理，以此为基础构造一个公理系统，为了方便讨论此处“三”暂且认为数字3（古文中的三意为多），于是：

公理1：对任意Ai，Aj，Ak.  {Ak，Aj}中至少存在一个元素为Ai的“师”.

接下来来证明韩愈“弟子不必不如师，师不必贤于弟子”的理论。那么什么是“贤”？韩愈也没有加以定义，事实上，他在论述的过程中，已经有一定经验作为论述基础，这种经验常见到众所周知，不需要点出即是如下：

公理2：(可比性)对平面任意两点A，B，则A“贤于”B或A不“贤于”B.
公理3：(传递性)若A“贤于”B，B“贤于”C，则A“贤于”C.

有了这些理论做支撑，就可以对他的结论加以证明.当然文学上“不必”二字的表述要换成存在性的探讨，如下：

定理1：平面内必存在一点A与其“师”A₁，使A“贤于”A₁.

定理1的证明：(反证法)
若对平面内任意一点A及其“师”A₁，总有A₁“贤于”A.(反设)
任取A₁，A₂，A₃三点(选择公理)
对于A₁，在{A₂，A₃}中，不妨设A₁→A₂存在(公理1)
由反设知，A₂“贤于”A₁，∴A₁不为A₂的“师”
∴对于A₂，只能A₃为A₂的“师”(公理1)
∴A₃“贤于”A₂  ∴A₃“贤于”A₁(公理3)
则在{A₁，A₂}中找不到A₃的“师”，这与公理1矛盾，因此定理1得证.

事实上，上面的证明过程可以用极端原理轻松解决，用大白话来讲就是
三个人中必存在一个最厉害的，那他在这三个人当中找不到自己的老师，导致矛盾...

其实值得我们注意的是，这个“贤”的比较依托于公理2和3，有点类似于“实数可以比较大小”的公理.那么这就从一个角度说明了韩愈理论的局限性，如果不承认公理2和3，把实数集推广到复数集，就没有什么大小比较之说，遑论贤与不贤.韩愈给出这个理论的同时，已经相当于承认人人之间是可以进行贤与不贤的比较的，这正是局限性所在.

Ⅱ
其实，公理1是一个非常好玩的公理，在它的基础上，我们可以发现平面内很多点的关系.

定理2.1  对任意3个点及另一点A，该3点中总至少有2个点为A的“师”.

这感觉跟废话一样，用大白话说就是其他三个人当中至少有两个是你老师嘛，这里就不加赘述了.更关键的，可以做出如下推广：

定理2.2   对任意n个点(n≥3)及另一点A，该n点中总至少有(n-1)个点为A的“师”.

定理2.2的证明：(数学归纳法)
n=3时，即定理2.1，命题成立.
若n=k（k为不小于3的自然数）时，命题成立，则当n=k+1时任取这些点中的一点B，那么剩下k个点中至少有(k-1)个A的师.若k个点均为A的“师”，则已成立.否则，就只有一点不为A的“师”，设为C，∵{B，C}中有A的“师”，∴B为A的“师”  ∴这(k+1)个点至少有k个点为A的“师“.
∴若n=k(k≥3)时命题成立，则n=k+1时命题成立
因为n=3时命题已成立，所以该命题对所有n≥3的自然数成立.

这就是著名鼎鼎的数学归纳法，它的理论依据是皮亚诺(Peano)公理的第五公理，归纳公理.

定理2.2带给人的感觉是，满世界的人都是你的老师，全班假设70人，除去你还有69人，他们当中至少有68个是你的老师  ...有点小不可思议，但这是从孔子那推出的，其实还能推出其他好玩的结论

定理3.1  4个点中，必存在2个点使该两点互为对方的“师”.

（接下来下面的定理的证明会涉及一丝图论知识）
定理3.1的证明:在K₄完全图中，连线段条数为C₄²=6，由定理2.2知4个点中共连出有向线段条数至少为4(4-2)=8，任两点间连接的有向线段至多两条，由抽屉原理知命题成立.

类似于上述证明方法，对Kn完全图，连线段条数C(2，n)=½n(n-1)，有向线段总条数至少为n(n-2)
设f(n)=n(n-2)-½n(n-1)=½(n-3)n              (#)

(#)表明，n≥4时，就存在“互师”情况了，更一般地，我们有

定理3.2  n≥4时，对任意n个点，必存在½n(n-3)个集合{Ai，Aj}，使Ai→Aj与Aj→Ai同时存在.

举一个通俗的例子，宿舍有7个人，那个7个人当中，就至少有½(7-3)*7=14对舍友，他们互为对方的老师，70个人的话就有2345对...

Ⅲ
在Ⅰ和Ⅱ的讨论中，我们基本构建了一个有向图的模型，接下来，我们简单讨论一下图论中的Euler迹问题.

Euler迹问题即是一笔画问题，始于历史上的哥尼茨堡七桥问题，我们本章的讨论，会稍微参考先贤的结果。类似于对Euler迹的定义，在此次讨论中，我们这样来定义：

定义2  有向图G中定点与有向线段交错排列的序列          
C：      A1   v1  A2  v2...An  vn  An+1 ,                               若任意vi(i=1,2,3,...,n）都是由Ai指向Ai+1的有向线段，且vi(i=1,2,3,...,n）两两不同且取遍图G中所有有向线段时，称序列C是图G的一条Euler迹.

在正式讨论之前，我们回顾Euler的结果，并加以利用（源于百度）

引理4   设G是一个连通图，则G存在Euler迹的充要条件是G中有且仅有两个奇次顶点或G中全是偶次顶点.

这里的奇次顶点与偶次顶点指的是顶点连接的线段条数为奇（偶）数的顶点个数，当我们在研究有向图时，由于要考虑方向性，因而这样的描述不过精准，我们借以下定义加以研究：

定义3  对于有向图G中的一点A，记G（A）为图G中以A为始端的有向线段的条数，称为正度.记g（A）为图G中以A为终端的有向线段的条数，称为负度.记M（A）=G（A）-g（A），称为合度.

类似于引理4，我们可以得到这样的结论

定理4.1 有向图G存在Euler迹的充要条件是对于图G中任意的一点A，都有M（A）=0或其中仅存在两点B1，B2使得M（B1）=1，M（B2）=-1且对其余的任意一点A，都有M（A）=0.

定理4.1的证明  
必要性 若有向图G存在Euler迹，不妨设其中一条为

C：   A1   v1  A2  v2...An  vn  An+1 ,

若A1与An+1为同一个点，则C中每出现一个点B，都同时是一条有向线段的起点和另一条有向线段的终点.从而对于图G中任意的一点Ai，都有M（Ai）=0  （i=1，2，...n，n+1）；否则M(A1)=1,M(An+1)=-1.必要性得证.
补充性质   由该证明我们注意到：若有向图G存在Euler迹

C：   A1   v1  A2  v2...An  vn  An+1，
⑴若对于图G中任意的一点Ai，都有M（Ai）=0
则A1=An+1，且若在C中用i+1代替i（约定vn+1=v1，An+2=A1），仍可得到新的Euler迹，仿造此操作，我们知道此时Euler迹的起点可以是任意一个点.
⑵若M(A1)=1,M(An+1)=-1且M（Ai）=0  （i=2，3，...n-1，n）则该图的Euler迹只有一条，且必以A1为起点，An+1为终点.
充分性（数学归纳法） 对有向图G中的有向线段条数n进行归纳，n=1时不证自明.若n=k时满足命题，则n=k+1时，若图G中对于任意的一点A，都有M（A）=0，则去除任意的P，Q两点的有向线段（不妨设为P指向Q）v0，得到图G′，此时M（P）=-1，M（Q）=1，由归纳假设及补充性质⑵知图G′存在Euler迹：C ：  Q  v1 A1...vm  P，
则图G存在Euler迹：C′ ：  P v0 Q v1 A1...vm  P
若图G中存在M（A）=1，M（B）=-1 ，则去除以A为起点的任一条有向线段，同理可以构造出图G的一条Euler迹.因而充分性得证.

笔者在定理4.1充分性的证明此处颇费心思，道理本身直观，然而要说明白挺难.亦可这样思考，构造一个自由点，让其在有向线段上移动，每经过一条有向线段视为该有向线段消失，则每经过一个点图G中的点的合度情况不变，从此角度也可证明，然而用数学归纳法，可以使语言更清晰严谨.无奈笔者能力有限，证明步骤略显冗长.