Discrete Mathematics-mid term

1. 对于任何简单无向图：点连通度<=边连通度<=smalldelta(G)
2. 握手定理：2m=∑d(vi)
3. 生成子图：少边不少点  子图：少边也可以少点
4. 边连通度：最小边割集的大小（其中边的数量）
5. 设G为n阶k-正则图，证明：G的补图也是正则图。（使用dG(vi)+dG'(vi)=n-1，为n-k-1-正则图)
6. 不含有奇圈-二部图
7. 在完全二部图中Kr,s中，加上C(r,2)+C(s,2)可以得到完全图
8. n阶非联通图的边数至多为:(n-1)(n-2)/2条（此时为2-连通）
9. 设9阶图G中，每个顶点的度数不是5就是6，证明：至少有5个6度顶点或者至少有6个5度顶点。（可以使用枚举法，通过总共的d加起来必须是偶数进行证明）
10. 证明：三维空间内不存在有奇数个面并且每个面都有奇数个棱的多面体。（反证法：假设存在这个多面体，则假设有图G=<V,E>，其中的V表示面（这里用点表示），而E表示两个面形成的棱，这样可以发现所有的度数相加是奇数（奇数个奇数之和还是奇数），违背了握手定理）
11. 现在有三个四阶的4条边的无向简单图，证明至少有两个同构（四阶四边无向，度数分布只有两种，根据鸽巢原理，一定至少有两个是同构的）
12. 假设G为n阶自补图，证明n=4k或4k+1（必有(n-1)n=2*k，其中k表示的是G中的边数，同时要说n-1和n互素）（自补图：补图和自己同构的图）
13. 设G1和G2为无向简单图，G1'和G2'为其补图，证明：G1和G2同构当且仅当G1'和G2'同构。证明：先从左向右证明,V(G1)=V(G1')=V1,V(G2)=V(G2')=V2,由于G1和G2同构，则必有一个双射f：V1->V2，使(u,v)∈E(G1)（任意u，v∈V1）时有(f(u),f(v))∈E(G2)，则有(u,v)∉E(G1)有(f(u),f(v))∉E(G2)，这样一来就有(u,v)∈E(G1')->(f(u),f(v))∈E(G2')即其补图同构,而从右向左证明只需要将第一个式子里的G换成G'即可
14. 设e为无向图G中的一条边，证明e为桥当且仅当它不在任何圈中。
15. 设e=(u,v)为无向图G中的一桥，证明v为割点当且仅当其不为悬挂顶点（可以用反证法证明）
16. 设2<=r<=s则在完全二部图中，含有r-1个圈，至多有s个顶点不相邻，至多有r个边不相邻，点连通度=边连通度=r
17. 设G为六阶无向简单图，证明G或者其补图存在三个顶点彼此相邻。（首先根据鸽巢原理，在G或者其补图中，一个点v至少和3个点相邻，再进行后面的证明）
18. 证明：若G不连通，则其补图G'连通
19. 证明：若G连通并且G的每个顶点的度都是偶数，则对任意v∈V(G)，均有w(G-v)<=d(v)成立

1. 欧拉图：无向图G为欧拉图，当且仅当其没有奇度的顶点
2. 哈密顿图：
充分条件：当任意不相邻顶点满足：d(u)+d(v)>=n则为哈密顿图
必要条件：若为哈密度图，则必有w(G-V)<=|V|
5. 完全图Kn中有(n-1)!条不同的哈密顿回路
6. 在k个长度大于等于3的圈构成的图中，再加上k条新的边即可构成欧拉图
7. 设G是恰好含有2k（k>=1）个奇度顶点的无向连通图，证明G中存在k条边不重的简单通路L1,L2,….Lk使得E(G)=∪E(Li)(数学归纳法，见书，任取两个奇度点使用归纳假设)
8.  说明当边数m=(n-1)(n-2)/2+1时，图不一定是哈密顿图（取一个Kn-1，再在外面放一个点和其完全图中任意一个点相连）
9. 设G为无向图，C为G中的一个圈，若从C上删除任何一条边后，C中剩下的边构成的路径都是G中的最长路径，证明：C为G中的哈密顿回路（只需要证明所有的点都在这个圈上面）
10. 只有含有闭欧拉迹的图才叫欧拉图，否则不叫欧拉图

1. 如果e为无向连通图G中的一条边，e在任何生成树中，则e为桥，如果e不在任何生成树中，则e为环
2. 设T为k+1阶无向树，k>=1，G为无向简单图，已知smalldelta(G)>=k，证明：G中存在与T同构的子图（数学归纳法，取树中的悬挂点去掉后使用归纳假设）
3. 设T1,T2为无向树T的子图，并且都是树，又有E(T1)∩E(T2)≠∅，证明：导出子图G(E(T1)∩E(T2))也是树。（已知没有圈，只用证明是联通的，在T上任意取两个点u,v即可）
4. 设G为n(n>=5)阶简单图，证明G或者其补图必含有圈

1. 定义：设G是一个平面图，如果G的任何两边不在顶点之外相交，那么称为平面图
2. 对于平面图G，有∑deg(R)=2e(G)其中R为G的面
3. 欧拉公式：p-q+r=2（p为顶点数，q为边数，r为面数）
4. 设G为p阶平面图，且其每个面次数至少为n，则q=e(G)<=(p-2)n/(n-2)
5. 根据上面的公式可以知道，K5不是平面图，K3,3也不是平面图
6. 正多面体只有五种：4、6、8、12、20
7. 设图G中e=uv为一条边，删去边uv，引入新的顶点w再连接uw和vw，称为引入2度顶点，反之，则为消去二度顶点，如果对G进行若干次引入或者消去二度顶点后得到H，那么就说G、H同胚
8. 无向图G为平面图<-->它不含同胚于K5或K3,3的子图
9. 推论：设G为简单平面图，有m<=3n-6（m为边数，n为点数）