Question

请问老师，在完全图K4的所有非同构生成子图中，有（ ）个是有三条边的？

如题，选项是A.1 B.2 C.3 D.4

Answer 1

C.3
－－－－－
3条边，总度数是6，分配到四个点上去，度数序列有三种情形：3111，2220，2211。在同构的意义下，每种情形只能画出一个图。

追问

老师非常感谢！顺便再问一下格尼斯堡7桥问题最少要拆几座桥？是三座吗？

追答

去掉两座桥就可以保证一次走遍所有桥且每座桥只经过一次。两个相邻的3度点之间去掉一边，剩下的两个顶点之间去掉一边，剩下的图可保证每个顶点的度数为偶数。