单射，则f是单射吗？说明理由。解：f是单射。假设f不是单射，则x1x2X使得fx1fx2于是
gfx1gfx2即gfx1gfx2。
这与gf是是单射矛盾，所以f是单射。8．是否存在一个同时不满足自反性，对称性，反对称性，传递性和反自反性的二元关系？解：存在。设Xabc，R是X上的二元关系Raaacabca。9．设R是X上的二元关系，证明：RR1是对称的二元关系。证：证ⅠRR11R1R11，故RR1是对称的。证ⅡxyRR1，xyR或xyR1，yxR1或yxR。则即
2
f于是yxRR1，因此RR1是对称的。10．设R是X上的二元关系，试证：RRRRR。证：RRRR0RR2RR2R3R。
RRR0RR2RRR2R3R
11．是否存在X（X
）上的一个二元关系R使得RR2R
两两不相等。解：存在。设X123
，是X上的二元关系且R1223
1
即可。R12设R是A上的一个自反关系，证明：是等价关系若abR且acR，R则bcR。证：R是A上的等价关系。若abR且acR，由R的对称性有：baR且acR，由R的传递性有：bcR
R是自反的，故aA有aaR。
若abR，由aaR有baR，所以R是对称的。若abR且bcR，由R的对称性有：baR且bcR，故由题意得acR，所以R是传递。因此，R是A上的等价关系。13．任意非平凡树都是偶图。证：任一非平凡树无圈，即圈长为零，零是偶数，所以任一非平凡树都是偶图。14．证明具有奇数个顶点的偶图不是哈密顿图。证：设GV1V2E，因为G有奇数个顶点，故V1≠V2。（1）若V1＞V2，则wGV2V1＞V2，由定理知，G不是哈密顿图。（2）若V1＜V2，则wGV1V2＞V1，由定理知，G不是哈密顿图。综上可知，G不是哈密顿图15列出无向树的特征性质（至少5个）。答：1G是树，即G是连通且无圈的无向图；2G任两不同顶点间有唯一路；3G连通且pq1；4G无圈且pq1；5G无圈且任加一边有唯一圈；6G连通且任去一边得不连同图。16．一棵树T有
2个度为2的顶点，3个度为3的顶点，
…，k个度为k的顶点，
则T有多少个度为1的顶点？
3
f解：设T有x个度为1的顶点。由r