首先,我们知道一个完全图Kn有n(n-1)/2条边,而一个K4有6条边。如果我们想在Kn中找到尽可能多的没有公共边的K4,我们需要最大化K4的数量,同时确保它们不共享任何边。
假设我们在Kn中找到了m个没有公共边的K4,那么这m个K4总共会使用6m条边。显然,6m不能超过Kn的总边数,即:
6m ≤ n(n-1)/2
现在,让我们考虑一下什么时候可以达到这个上界。如果6m = n(n-1)/2,那么Kn的每一条边都恰好属于一个K4。这只有在以下两种情况下是可能的:
当n是4的倍数时,我们可以将Kn的顶点分成n/4组,每组4个顶点,然后在每组内构造一个K4。这样,我们就得到了n/4个没有公共边的K4,且它们恰好覆盖了Kn的所有边。
当n是4的倍数加1时,我们可以先选择任意一个顶点,然后将剩下的n-1个顶点分成(n-1)/4组,每组4个顶点,在每组内构造一个K4。这样,我们就得到了(n-1)/4个没有公共边的K4,它们加上任意选择的那个顶点,恰好覆盖了Kn的所有边。
对于其他情况,我们无法恰好覆盖Kn的所有边,因此m会小于上界n(n-1)/12。
综上所述,完全图Kn中最多可以找到的没有公共边的K4的数量为:
当n ≡ 0 (mod 4)时,最多有n/4个K4; 当n ≡ 1 (mod 4)时,最多有(n-1)/4个K4; 当n ≡ 2 或 3 (mod 4)时,最多有⌊n(n-1)/12⌋个K4。这里的⌊x⌋表示x的下取整。
假设我们在Kn中找到了m个没有公共边的K4,那么这m个K4总共会使用6m条边。显然,6m不能超过Kn的总边数,即:
6m ≤ n(n-1)/2
现在,让我们考虑一下什么时候可以达到这个上界。如果6m = n(n-1)/2,那么Kn的每一条边都恰好属于一个K4。这只有在以下两种情况下是可能的:
当n是4的倍数时,我们可以将Kn的顶点分成n/4组,每组4个顶点,然后在每组内构造一个K4。这样,我们就得到了n/4个没有公共边的K4,且它们恰好覆盖了Kn的所有边。
当n是4的倍数加1时,我们可以先选择任意一个顶点,然后将剩下的n-1个顶点分成(n-1)/4组,每组4个顶点,在每组内构造一个K4。这样,我们就得到了(n-1)/4个没有公共边的K4,它们加上任意选择的那个顶点,恰好覆盖了Kn的所有边。
对于其他情况,我们无法恰好覆盖Kn的所有边,因此m会小于上界n(n-1)/12。
综上所述,完全图Kn中最多可以找到的没有公共边的K4的数量为:
当n ≡ 0 (mod 4)时,最多有n/4个K4; 当n ≡ 1 (mod 4)时,最多有(n-1)/4个K4; 当n ≡ 2 或 3 (mod 4)时,最多有⌊n(n-1)/12⌋个K4。这里的⌊x⌋表示x的下取整。
