38下面两图是否同构? 39.讨论下列三个图的同构性 40.证明: Peterson图与下列图同构 41.已知n阶简单图G有m条边,各顶点的度数均为3,(1)若m=3n-6,证明G在同构意义下 唯一,并求m,n;(2)若n=6,证明G在同构意义下不唯一。 42若图G有n个顶点,n-1条边,则G一定是树吗?说明理由 43证明非平凡树中最长路的起点和终点都是叶子(1度点)。 44证明恰有两个叶子的树必是路。 45证明:若G是树且Δ≥k,则G至少有k个1度顶点 46证明每个树都是二部图。 47设n表示树T中度为i的顶点的个数。(1)证明对非平凡树T的叶子数n1有下面公式成立 2+n2+2n+3n+…=2+∑(-2)38. 下面两图是否同构？ 39. 讨论下列三个图的同构性 40. 证明：Peterson 图与下列图同构 41. 已知 n 阶简单图 G 有 m 条边，各顶点的度数均为 3，(1) 若m n = 3 6 − ，证明 G 在同构意义下 唯一，并求 m n , ；(2) 若 n = 6 ，证明 G 在同构意义下不唯一。 42 若图 G 有 n 个顶点， n −1条边，则 G 一定是树吗？说明理由。 43 证明非平凡树中最长路的起点和终点都是叶子（1 度点）。 44 证明恰有两个叶子的树必是路。 45 证明：若 G 是树且 Δ ≥ k ，则 G 至少有 k 个 1 度顶点。 46 证明每个树都是二部图。 47 设 i n 表示树 T 中度为 i 的顶点的个数。(1) 证明对非平凡树 T 的叶子数 1 n 有下面公式成立： 1 345 3 2 2 3 2 ( 2) i i n nnn in ∞ = = + + + +⋅⋅⋅ = + − ∑ . d a c b h g e f v1 v2 v8 v7 v6 v5 v4 v3 u v t s z y x w