是一个图，结点集合为V，边集合为E，则
G的结点度数
等于边数的两倍．
4．设有向图D为欧拉图，则图D中每个结点的入度等于出度
．
5．设GV，E是具有
个结点的简单图，若在G中每一对结点度数之和
大于等于
1
，则在G中存在一条汉密尔顿路．
6．设无向图G＝V，E是汉密尔顿图，则V的任意非空子集V1，都有
WGV1
V1．
7．设完全图K
有
个结点
2，m条边，当当m2

时，K
中
存在欧拉回路．
8．设图GVE，其中V
，Em．则图G是树当且仅当G是连通的，
2
f★形成性考核作业★
且m
1
．
9．连通无向图G有6个顶点9条边，从G中删去4
能得到G的一棵生成树T．
10．设正则5叉树的树叶数为17，则分支数为i4
条边才有可．
三、判断说明题（判断下列各题，并说明理由．）1．1如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．2图G1，如下图所示是欧拉图．
解：1错，图G是无向图，当且仅当G是连通的，且所有结点度数均为偶数，这里不能确定G图是否是连通的。
2对，由欧拉图的定理“无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点”得到，这里可找到如下一条欧拉回路v4v5v2v6v4v1v2v3v4。
2．图G2（如下图所示）不是欧拉图而是汉密尔顿图．
解：对，由欧拉图的定理“无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点”，这里结点abdf的度数都为奇数；它是汉密尔顿图，因为找到了如下一条汉密尔顿回路abefgdca。
3．1设G是一个有7个结点16条边的连通图，则G为平面图．2设G是一个连通平面图，且有6个结点11条边，则G有7个面．
解：1错，没有提到面。2对，由欧拉定理得到：结点边面2，即为连通平面图，这里61172
3
f4．下图给出的树是否同构的．
★形成性考核作业★
解：a不与b、c同构，但b、c同构。因为由图的同构相关联，得到同构的必要条件：1结点数目相同；2
边数相同；3度数相同的结点数目相同。
四、计算题
1．设GV，E，Vv1，v2，v3，v4，v5，Ev1v3，v2v3，v2v4，v3v4，
v3v5，v4v5，试
1给出G的图形表示；
2写出其邻接矩阵；
3求出每个结点的度数；解：1G的图形如下
4画出其补图的图形．
00100001102G110110110100110
3v1度数为1，v2度数为2，v3度数为4，v4度数为3，v5度数为2
4其补图的图形如下
2．图GVE，其中Vabcdr