习题一：
? 4. 证明下面两图同构。 v u u v u v vv u vu u v v u u v u u v (a) (b) 证明:作映射f : vi ? ui (i=1,2….10)
容易证明，对?vi v j ?E ((a)),有f (v i vj,),?,ui,uj,?,E,((b)) (1? i ? 10, 1166210 557 2889103443791?j? 10 ) 由图的同构定义知，图(a)与(b)是同构的。? 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m，则有： m=0:
m=1 ：
m=2：
m=3：
m=4：
m=5：
m=6：
因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ? 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）
不是图序列。
证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列；
（6,6,5,4,3,3,1）是图序列
?1?(d2?1,d3?1,,dd?1?1,dd?2,,dn)是图序列
11（5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ?
12.证明：若
，则包含圈。
证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干个连通的情形来证明。设
,对于中的路
若与邻接，则构成一个闭路。若是一条路，由于，因
此，对于?
，存在与之邻接，则构成一个圈。
17.证明：若G不连通，则连通。
,若与属于G的连通分支，显然与在中连通；
证明：对于任意的
若与属于的同一连通分支，则与分别在中连通，因此，与在中连通。 ?
18..
证明：若为
=
证明：若,则
的割边，则，所以，若
=，则有
，若为的非割边，则
.
