证明或证伪：非完全连通图中满足特定邻接关系的三顶点存在性

问题1：非完全连通图中是否存在三个顶点a、b、c，使得a与b有共同邻居c？ #

结论：该命题不成立——存在非完全连通图不存在这样的三元组

反例：3个孤立顶点构成的无边图。

• 这个图是非连通的（属于“非完全连通图”范畴），所有顶点没有任何邻居；
• 任意两个顶点都找不到共同邻居，自然不存在满足条件的a、b、c。

如果限定为连通但非完全的图，命题则成立：
连通非完全图中必然存在度数≥2的顶点（否则图只能是单条边或孤立点，前者是完全图，后者不连通）。取该顶点x的两个邻居a、b，x就是a和b的共同邻居，直接满足条件。

问题2：非完全连通图中是否存在三个顶点a、b、c，满足a邻接b、b邻接c，但a与c不邻接？ #

结论：该命题不成立——存在非完全连通图不存在这样的三元组

反例：两个不相交的完全图K₃组成的图。

• 这个图是非连通的（属于“非完全连通图”范畴）；
• 任意三个顶点的邻接关系只有两种：
  1. 三个顶点在同一个K₃内：两两相邻，不可能出现a邻接b、b邻接c但a不邻接c的情况；
  2. 两个顶点在一个K₃，第三个在另一个K₃：仅同K₃内的一对顶点相邻，无法形成a-b-c的邻接链。

反证法思路补充 #

假设不存在问题2描述的三元组，意味着图中任意两个有公共邻居的顶点必须相邻。这种结构的图只能是若干个完全图的不交并——如果有跨完全图的邻接边，会导致公共邻居出现，违背假设。而这类不交并图（只要包含至少两个完全图）就是非完全连通图，且不存在问题2中的三元组，直接证伪原命题。

内容的提问来源于stack exchange，提问作者advance