Suppose a graph G is a tree containing only odd-degree verti

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/10/01 19:53:29

Suppose a graph G is a tree containing only odd-degree vertices where each vertex has degree at most 7 and G has exactly 10 leaves
a) what is the maximum number of vertices that G can have?Prove your result is true.
b）what is the minimum nuber of vertices that G can have?Prove your result is true.
恩专有名词不确定对应的中文是什么差不多是图G是树图,每个顶点（vertex）都是奇数个degree,degree最大是7,图G有恰好10个leaves
求G最大的顶点数（vertices）和最小的顶点数（vertices）.并证明

(a) 这里degree at most 7暂时用不上.先考虑G有两个叶子结点的情况,那么至多有4个顶点（列举即可）.现在归纳证明对于有n个叶子结点的odd-degree（偷懒的叫法）树,它至多有2n个结点.
该命题对n=1和n=2成立.
假定对于n-1成立,那么对于有n个叶子结点的odd-degree树,找离根最远的一个叶子,它必须有至少一个兄弟,否则它的父结点的度数是2,不是奇数.它这个兄弟必须也是叶子,否则它这个兄弟的子结点比它离根更远.把它和它的兄弟拿掉,剩下的树仍然是odd-degree的,可能有n-2或者n-1个叶子（如果它没有其它兄弟,那么它的父亲就会变成叶子,这时候是n-1,否则是n-2）,于是剩下的这颗树,按归纳假设,至多有2(n-1)个结点,那么去掉这两个叶结点之前,至多有2n个结点.
这样的树容易构造.只要做一个二叉树,每对兄弟结点里都只有一个有孩子结点就行了.
这样至多20个结点.
(b) 12个结点.根结点有6个孩子,其长子有6个孩子,无其它结点.
有10个叶结点的树,再加上根,至少11个结点.但如果只有11个结点的话,那么根的度数就是10,大于7,所以不可能.

Write a formula for the third degree polynomial whose graph A graph is embeddable in a plane,if and only if it is embedd Is a four-year degree the only path to a secure future?翻译 [A trinomial has only one variable x and its degree is 2]意思是 a pair of odd Combustion of a 0.9835-g sample of a compound containing onl a graph is symmetric with respect to the y-axis Assume f is a differentiable function whose graph passes thr the production possibilities frontier is a graph showing the there is a little bird in the tree,but only a little peopie 英语翻译Odd though it sounds,cosmic inflation is a scientificall 英语翻译When a metal is immersed in a solution containing its ow