Question

一个离散数学问题

设无向简单图G有9个结点。证明：G中至少存在两个度数相同的结点。

Answer 1

如果结点的度数是指和结点相连的边数的话，
可以用反证法：假设这9个结点没有度数相同的，我们来给结点编号，度数为i的结点编号为ai，因为只有9个结点，则因为无向简单图不允许有平行边和自环，所以每个结点最多只能连接8个不同的结点，所以度数最多只能是8，而最少的自然是0，因为需要给9个点编号，所以只能从a0到a8，但如果存在a0，则表明结点中有一个和其它结点都不相接，所以最大的偏号只能到a7，但a0到a7只能给8个不同度数的结点编号，所以至少有1个度数和a0到a7中的一个结点度数相同。所以只有9个结点的无向简单图至少有两个度数相同的结点。

不知这样算不算证明了？

追问

答案和你的证法差不多，但是还不太理解。

Answer 2

设p为天下雨，q为他乘车上班。
1）q→p；由果索因。
2）-p→-q，（-为“非”的意思，下同），相当于“如果天不下雨，他就不乘车上班。”
设s为2是素数，r为4是素数。
3）-（p^q）；
4）-（-（p√q）），√是“或”的意思。