习题一
2.
假设G存在孤立节点，不妨设其编号为n，则1…n-1号点的度数最大为n-2，则m<=(n-1)(n-2)/2，这与m>(n-1)(n-2)/2矛盾，则原命题成立。
6.
证明9个人中如果不存在4人互相认识，则存在3人互相不认识。
反证法。假设不存在4人互相认识，也不存在3人互相不认识(*)。从9人中任选一人，称为A.
Lemma 1：A至少认识5人。
反证法。假设A至少不认识4人，称为BCDE，则BCDE至少两人不认识，设为BC，则ABC互相不认识，与(*)矛盾。
Lemma 2：A至多认识5人。
反证法。假设A至少认识6人，称为BCDEFG。课上已证明：6个人中，如果没有 3 个人互相认识，则至少有 3 个人相互不认识。由(*)知不存在3个人互相不认识，则有3个人互相认识，设为BCD，则ABCD互相认识，与(*)矛盾。
Proof：综上，A认识恰好5个人。对所有人应用以上结论，则每个点度数为5，总度数9×5=45，不是偶数，矛盾。因此原命题成立。
8.
邻接矩阵
| 0 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
关联矩阵
| 1 | 1 | 0 | -1 | 0 | 0 | -1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|
| -1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | -1 | 0 | -1 | 0 |
| 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | -1 |
| 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
边列表
A (1 1 2 3 3 5 6 6 6)
B (2 4 5 1 4 3 1 3 4)
正向表
A (1 3 4 6 6 7 10)
B (2 4 5 1 4 3 1 3 4)
习题二
1.
设k个联通支为。显然在集合大小不变的情况下，每个连通图内部均为完全图时，边数最多。记
，则当前边数为
。即最大化
。假设对某个
有
，则有
，即，将点从小集合移至大集合，使总边数增加。因此边数最多的图含有一个大小为
的完全图，和
个孤立点。经计算，边数最多为
.
2.
不妨设G不连通，存在k个联通支，组成k个集合，不妨设1…k号点对应属于
。则对于
，属于不同集合的两点间有边（无需考虑
中相同集合的点之间的边）。因此，1号点和不属于
的点都有边，2号点和属于
的点都有边，1和2有边，因此
联通。
3.
反证法。假设两条不相交道路的点分别依次为a1a2…ak, b1b2…bk（长度为k-1）。由于G联通，不妨ai, bj之间联通，即，存在道路aic1c2…ctbj，其中c1…ct不在{ai}, {bi}中（若c1中含有{ai}中的点ax，则不妨令ai=ax；含有{bi}中的点的情况同理）。则考虑道路a1a2…ai…bj…bk和b1…bj…ai…ak，由于互补性，这两条道路的长度之和一定为2(k-1)+2(t-1)，因此存在一条长度大于k-1的道路，矛盾。
4.
在简单图中，若n>=4, m>=2n-3，则G中含有带弦的回路。
Lemma：如果简单图G的一条极长初级道路的一个端点的度数>=3，则G存在带弦回路。
不妨设道路的点依次为a1…ak，其中d(a1)>=3。由最长道路可知，与a1相连的点必须在此道路上。设与a1相连的另外两点为ai, aj (i<j)，则a1a2…aja1为一个回路，(a1, ai)为它的弦。证毕。
Proof：数学归纳法。当n = 4时，命题显然成立；假设命题对于n = k时成立，考虑n = k + 1，即考虑对于顶点数是k + 1，边数大于等于2(k + 1) − 3的图G。设Γ是G的一条极长初级道路，v是Γ的一个端点， 如果d(v) ≥ 3，则引理可得G有带弦回路，否则（即d(v) < 3）G − v是有k个顶点， 边数>=2(k + 1) − 3 − 2 = 2k − 3的图，根据归纳假设，G − v含有带弦回路，那么G也必含有带弦回路。
5.
对任意 n 个结点、m 条边的简单图 G，若 G 不含 K3，则且m ⩽ n^2/4 .
考虑G的每一条边(a, b)。由于G不含K3，则(d(a)-1)+(d(b)-1)<=n-2（否则一定存在含a, b的三元环），故d(a)+d(b)<=n。对所有边应用此结论并求和，得到。
由Cauchy不等式，
即，