Question

一道离散数学 图论的题目，求助。

题目为：
含有5个结点，3条边的不同构的简单图有___个。
A 2 B 3 C 4 D 5

PS:有什么公式可以套公式直接算出来么？有的话请把公式告知。
没有公式的话请详细说下思路，主要是我不知道什么叫不同构，迷糊。要思路，怎么想的，别光给答案。

初学，知道的朋友帮助下，满意追加分数！

Answer 1

简单图：无环、无多重边的图。

同构图：两个同阶图（点数为图的阶），若定点集合与边集合之间在保持关系性质条件下一一对应，则为同构。

公式不知道，但是思路个人认为是列举法。

一共5点3边，且为简单图故必有一点有两边（及此点次为2）：

一是有一点次为3，故每点有2种可能，共10.（但是若题意是将各点视为同样则为1种）。

二是有一点次为0切无次为3的点，则每点仅有1种可能，共5.（但是若题意是将各点视为同样则为1种）。

三是有一点此为2，其余全是1，则每点仅有1种可能，共5.（但是若题意是将各点视为同样则为1种）。

故答案为B

Answer 2

设G是一个n个顶点的简单图，若G含孤立顶点，则它的最大度不超过n-2，由鸽笼原理，一定存在两个点的度数相同；若G不含孤立顶点，则它的最小度大于等于1，最大度小于等于n-1，由鸽笼原理，也一定存在两个点的度数相同。