解: ∑dev(v,)=2e=2×21=42 12×3+(n-12)×2=42 n=15
解： 1 ( ) 2 2 21 42 12 3 ( 12) 2 42 1 5 n i i dev v e n n
3.已知m个结点的简单图G有e条边,各结 点度数为3,2n=e+3。试画出满足条件的 所有不同构的G ■提示:握手定理(西南交大2000考研/北京 大学1990考研) 参考1(2)
3. 已知n个结点的简单图G有e条边，各结 点度数为3，2n=e+3。试画出满足条件的 所有不同构的G。 提示：握手定理（西南交大2000考研/北京 大学1990考研） 参考1(2)
■解:由握手定理,e=(3n/2);由已知, e=2n2;所以n=6,e=9。 在同构意义下G不是唯一的
解：由握手定理，e=(3n/2)；由已知， e=2n-2；所以n=6 ，e=9 。 在同构意义下 G不是唯一的
4.设树T有17条边,12片树叶,4个4度 内结点,1个3度内结点,求T的树根的度 数 (提示:握手定理。北大1997考研)
4. 设树T有17条边，12片树叶，4个4度 内结点，1个3度内结点，求T的树根的度 数。 （提示：握手定理。北大1997考研）
■解:结点数为17+1=18 由握手定理,12*1+4*4+1*3+1*=34
解：结点数为17+1=18 由握手定理，12*1+4*4+1*3+1* l=34, l=3