证明:在有6个顶点12条边的连通简单平面图中,每个面由3条边围成。

若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。

简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。

设图G如题29图所示。(1)写出图G的邻接矩阵；(2)G中长度为4的通路有几条?(3)上问中有几条回路?

今有a、b、c、d、e、f、g共7个球类运动爱好者，已知下列事实：a喜欢篮球运动；b喜欢篮球运动和足球运动；c喜欢篮球、排球和乒乓球运动；d喜欢网球和足球运动；e喜欢羽毛球和排球运动i厂喜欢棒球、网球和乒乓球运动；g喜欢棒球和羽毛球运动。试问：这7个人应如何围圆桌排座位，才能使每个人和他身边的人有共同球类爱好话题。须写出所有可能方案。

今有a,b,c,d,e，f共6人,已知下列事实:a会讲德语、英语、法语和汉语;b会讲德语、朝鲜语和意大利语;c会讲俄语、意大利语、西班牙语和葡萄牙语;d会讲俄语、日语和法语;e会讲葡萄牙语、日语和英语;f会讲汉语、朝鲜语和西班牙语试问这6个人应如何排座位,才能使每个人和他身边的人用同种语言交谈?列出所有可能的排座方案。

小赵、小李、小钱、小孙参加数学建模竞赛,根据下列情况,确定4人中获奖的是哪些 人,未获奖的是哪些人。需写出推导过程。 (1)只要小赵或小钱中一人未获奖,小孙和小李就都得奖; (2)小孙没获奖或小李没获奖是不可能的; (3)小钱获奖了。

某开发区有新建的5个工厂,相互之间的距离由下列矩阵表示(单位为千米) 现要架设供电线路。请找出最短的供电线路铺设方,并算出该方案的线路长度。

对下面的带权图,回答下列问题。 (1)给出每个顶点的度。 (2)画出图的邻接矩阵。 (3)求图的一棵最小生成树。

证明:每个面至少有4条边围成的任何连通简单平面图中,m≤2n-4,其中n为顶点数,m为边数。