一个图论题

来源：百度知道 编辑：UC知道 时间：2024/05/26 20:10:03
平面中有100个点（任3点不在一直线上），证明，可以用2500条边把这100个顶点连成一个简单连通图，图中不存在以任3个点为顶点的三角形

这个多好证 用1到100编号这100个点.
并把这100个点排成两行 ，每行50个点，如下：
1 2 3 4 ...... 50 (第一行)
51 52 53 54 ......100 (第二行)
用第一行的任意一个数字和第二行的每一个数字相连,也就是说
(1,51),(1,52),(1,53)....(1,100) .....50组

(2,51),(2,52),(2,53)....(2,100) .....50组

........

(50,51),(50,52),(50,53)....(50,100) .....50组
一共有50*50=2500条边,是简单连通图 ,但是任意的三条不能构成三角形的