各位高手，有8道基础菜鸟级图论题亟待解决！！！

东京流浪猫

1、        拥有p个顶点，q条边，r个区域，kge连结成分的平面图G，满足等式p-q+r-k=1。证明之。
2、        K是奇数，请证明k正则图的顶点数为偶数。
3 _9 n* u! _/ H- _6 r$ |; k6 K3、        G是连通图。请证明G的任意两条最长路径都通过某个共同顶点。
! D. E5 q7 e' a: U  Q) h4 ?4、        G是顶点数4个以上的2连通图。请证明以下两个命题等价:
       (1)        从G删除相邻连接的顶点后将是非连通图；
    (2)        两顶点之间相连的边收缩后的图不是2连通图。
& X8 q! d* W, z& ]2 D* m) k3 Y* g3 b5、        请画一个不拥有1因子的3正则图。
8 V, j. J3 P/ p& A. w2 l0 X- t6、        请证明图K2，n的全域树的个数是n2n-1
" x3 ]$ p- w) m* T4 J% C9 j: d" G% }7、        G是平面图。请证明G的任意平面图不持有相互邻接的5个面（包括外面）。
) ?& F/ {% B, U  {8、        请画出拥有8条边且不包含三角形的最小顶点数的图。并证明这个图是最小顶点数的图，且有2个存在。
" a& [; o0 `: X6 }; N. w+ w5 X

喜新■tunesd

新手走过= =看看而已