完全图中无公共边的最大三角形数量求解

嘿，这个问题其实是图论里的边不相交三角形填充问题，我来帮你理清楚解法和结论～

核心思路 #

我们的目标是在完全图 (K_n) 中，找出最多的两两没有公共边的三角形（顶点可以重复，只要边不重叠就行）。本质上是把尽可能多的边划分到独立的三角形中，剩下的边如果没法组成三角形就只能留下。

分情况讨论（按顶点数n的奇偶性） #

1. 当n为奇数时 #

完全图 (K_n) 中每个顶点的度数是偶数（(n-1)，奇数减1是偶数），这意味着我们有机会把大部分甚至全部边都分解成三角形：

• 如果 (n \equiv 1) 或 (3 \pmod{6})：总边数刚好是3的倍数，可以实现完美三角形分解，所有边都能被分到不相交的三角形里。此时最大数量为：
  [
  t(n) = \frac{n(n-1)}{6}
  ]
  比如n=3（仅1个三角形）、n=9（共12个三角形）都符合这个情况。
• 如果 (n \equiv 5 \pmod{6})：总边数除以3余1，最多只能用掉总边数减1的部分来组成三角形，剩下1条边无法利用。此时最大数量为：
  [
  t(n) = \frac{n(n-1)-2}{6}
  ]
  比如n=5，总边数10，最多能找到3个不相交的三角形，剩下1条边。

2. 当n为偶数时 #

完全图 (K_n) 中每个顶点的度数是奇数（(n-1)，偶数减1是奇数），而每个三角形会给顶点贡献2度（偶数），所以每个顶点最多参与 (k-1) 个三角形（n=2k），因此最大数量的公式为：
[
t(n) = \left\lfloor \frac{n(n-2)}{6} \right\rfloor
]
举几个例子：

• n=6（你提到的例子）：代入公式得 (\frac{6×4}{6}=4)，也就是最多能找到4个两两无公共边的三角形。比如可以构造：
  • (1,2,3)
  • (1,4,5)
  • (2,4,6)
  • (3,5,6)
    剩下的边1-6、2-5、3-4两两不相交，没法组成三角形，所以确实是上限。
• n=4：代入得 (\frac{4×2}{6}≈1.33)，取整为1，也就是最多只能找到1个三角形——因为K4里任意两个三角形必然共享一条边，无法做到完全无公共边。

验证你的例子 #

你提到的两个三角形(1,3,4)和(1,5,6)确实符合要求，它们没有公共边；而(2,3,4)和(3,4,5)共享边3-4，所以不符合规则，这个判断是完全正确的。

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