我们将展示一些（多少有点难度的）图论问题。
计数类
例1
设 \(n\) 是正整数， \(G\) 有 \(12n\) 个顶点，每个顶点的度数都是 \(3n+6\) ，且任何两个顶点的公共邻点数相同，求 \(n\) 的值。
对这类计数类问题，常见的做法是进行算两次。对于公共邻点，常见的统计对象是三元组 \((u,v,w)\) ，其中 \(u\) 是 \(v,w\) 的公共邻点
我们知道对任何的 \(v,w\) ， \(u\) 的数量相同，设为 \(k\) ，三元组个数是 \(k\binom{12n}2\)
而对于 \(u\) ，选择 \(v,w\) 共有 \(\binom{3n+6}2\) 中方法，所以 \(k\binom{12n}2=12n\binom{3n+6}2\)
解得 \(k=\frac{(3n+6)(3n+5)}{12n-1}\)
于是 \(12n-1\mid (n+2)(3n+5)\) ，可以化简得到 \(12n-1\mid 25\cdot 21\) ，然后看到 \(12n-1=35\) ，于是 \(n=3\)
构造这样的图并不是很容易。我们设 \(36\) 个点是 \((0,0)(0,1)...(5,5)\) ，然后将横坐标或纵坐标相等的点全部连边，再将 \(x_1-y_1\equiv x_2-y_2\:(mod~6)\) 也即相同对角线（右上方向）的点连边。这个图满足要求。
例2
证明：任何含偶数顶点的图 \(G\) 中存在两个顶点有偶数个公共邻点。
假设任两个顶点只有奇数个公共邻点。我们考虑顶点 \(v\) 及其邻点 \(v_1,v_2,...,v_k\) 的诱导子图。其中 \(v_i\) 与 \(v\) 的公共邻点在 \(v_j(j\ne i)\) 中，并且是奇数个，所以它的度数是偶数。然后诱导子图的总度数（根据握手引理）是偶数，所以 \(v\) 的度数是偶数。我们考虑了所有邻点，所以 \(v\) 在原图中的度数就是偶数。
固定 \(u\) ，下面我们对 \((u,v,w)\) （两两不同）计数，其中 \(u,v\) 和 \(v,w\) 连通。我们先看到 \(u\) 的度数是偶数，所以有偶数种 \(v\) 的选择，然后有奇数种 \(w\ne u\) 的选择，这类三元组有偶数个。
但是 \(u,w\) 的公共邻点数是奇数，而 \(w\) 有 \(2n-1\) （假设图 \(G\) 有 \(2n-1\) 个顶点）种选择，导致这样的路径数应为奇数。这就矛盾。
例3
设二部图的顶点集为 \(X\) 和 \(Y\) ，每个点度数为正整数。对任何相邻的点 \(x\in X,y\in Y\) ，总有 \(d(x)\ge d(y)\) ，证明： \(|X|\le |Y|\)
法一：
经过一些思考不难想到，如果 \(d(x)=k\) ，这个 \(x\) 就限制了至少 \(k\) 个 \(y\) 的度数不超过 \(k\) 。但是如果 \(d(x)=k\) 的 \(x\) 数目达到了 \(n>k\) 呢？
我们首先知道对于这些 \(x\) ，任何 \(d(y)\ge k+1\) 的 \(y\) 不会与它们相邻，否则与题设条件矛盾。
事实上，若 \(d(y)\le k\) 的 \(y\) 的数目 \(<n\) ，根据抽屉原理就会发现某个 \(y\) 与 \(n+1\) 个 \(d(x)\le k\) 的 \(x\) 相邻，这就矛盾。
所以对任何 \(k\) ， \(d(x)\le k\) 的 \(x\) 的数目不少于 \(d(y)\le y\) 的 \(y\) 的数目。由于 \(\sum d(x)=\sum d(y)\) ，这能给出结果。
法二：
一个不太好想的做法是作一些求和：
\(|X|=\sum\limits_{xy\in E}\frac 1{d(x)}\le \sum\limits_{xy\in E}\frac 1{d(y)}=|Y|\)
例4
一次操作是指：选取图 \(G\) 中的一个 \(C_4\) ，然后去掉其中一条边。对 \(K_n\) 进行操作，问最后剩余边数的最小值是多少？
稍微对 \(K_4,K_5\) 作尝试，可以看出答案是 \(n\) 。最后会剩余 \(n-1\) 条边是显然的，因为删除圈上的一条边依旧保持连通（如果一条路径原来经过这条边，就改成经过这个圈的另外三条边），所以最后剩一棵树就没法删了。但为什么是 \(n\) 而非 \(n-1\) ？
我们注意到无论如何删除，图中都会剩余一个奇闭轨，从最开始的奇圈开始，若其中一条边被删除，就替换成 \(C_4\) 的另外三条边，保持奇数长度。（实际上是奇圈，但是圈在改边之后可能会成为闭轨，需要做一些缩减，表述起来麻烦）
而树是没有奇数长度的闭轨的，所以最后必须剩余 \(n\) 条边。
常见思考方式
我们会看到图论中很多的思维与组合中高度重合。
有一些常见的考虑对象：
-
一个顶点及其邻点。经常考虑度数最大/最小的点，或是最边缘的点（最长路径的端点，与其它顶点最短距离最大的点）
-
最长路径
-
图的极大子结构
例1
设图 \(G\) 有 \(2n+1\) 个顶点，任何 \(n\) 个顶点均存在一个公共顶点，证明：图 \(G\) 存在一个顶点与其余 \(2n\) 个顶点均相邻。
这个问题很困难，尽管过程非常简短。这样的题目在竞赛中不是很多见（本题来自全俄数学奥林匹克）。对 \(n=2,3\) 的情况画几个图也许能给出一些提示，但这些图都很乱，很难说能发现非常多的结果。
部分读者可能会尝试从 \(n\) 个点与它们的一个公共邻点出发，考虑剩下的 \(n\) 个点，但很快发现分类情况过多。这种方法失败的原因在于它思考的过于局部，如果局部的想法无法在几步内成功，通常来说就不是好的方法。
还有一个很难但是关键的想法。任何 \(n\) 个顶点存在公共邻点，说明任何 \(k\le n\) 个顶点都存在公共邻点。
然后我们可以证明存在一个 \(K_{n+1}\) 子图。实际上，任取两个相邻的点，然后取它们的公共邻点，再取这三个点的公共邻点，依此类推，最后取 \(n\) 个点的公共邻点得到 \(K_{n+1}\)
然后剩余 \(n\) 个点与 \(K_{n+1}\) 中某个点相邻，这个点满足题目要求。
例2
设图 \(G\) 满足：任何四个顶点 \(v_1,v_2,v_3,v_4\) 都存在 \(i\) 使得 \(v_i\) 与 \(v_{i-1},v_{i+1}\) 都相邻或都不相邻。证明： \(G\) 的顶点集可分为 \(A\) 与 \(B\) ，使得 \(A\) 中任两个点相邻， \(B\) 中任两个点不相邻。
法一：
这道题局部想法将会生效。我们选一个 \(u\) 放入 \(B\) ，然后把它的邻点 \(v_1,v_2,...,v_m\) 放入 \(A\) 。（之所以可以这样做，是因为 \(B\) 中一个点的邻点一定在 \(A\) 中。这不是我们的策略，而是必然的事实）
我们需要证明 \(v_iv_j\) 相邻。考虑 \(uv_iv_js\) 这样四个点，如果 \(v_j\) 和 \(s\) 相邻，但是 \(s\ne v_k\) ，那我们就成功了（可以看出这时只能 \(v_iv_j\) 相邻）
这个 \(s\) 一定存在吗？我们可以取 \(u\) 是度数最小的，那么对每个 \(v_i\) ，要么他与 \(u,v_k(k\ne i)\) 全相邻，要么能找到 \(s\) 。无论哪种情况都可以给出我们想要的结果
如果一个点只与 \(v_1,v_2,...,v_m\) 中点相邻，将它放入 \(B\) 。否则假设 \(s,t\notin \{u,v_1,v_2,..,v_m\}\) 相邻，我们考虑 \(uv_ist,usv_it\) ，其中 \(us,ut\) 均不相邻，所以 \(v_i\) 与 \(s,t\) 均相邻，这对每个 \(i\) 都成立，把 \(st\) 放入 \(A\) ，这样就完成了构造。
法二：
熟悉图论的读者也会尝试的方法是直接取 \(A\) 是最大的完全子图。
我们假设 \(B=V\backslash A\) ，然后假设 \(u,v\in B\) 相邻。我们说 \(A\) 的最大性表明， \(A\) 中必须有点 \(u'\) 与 \(u\) 不相邻，以及 \(v'\) 与 \(v\) 不相邻
如果 \(u'=v'\) 并且只有这一个选择，我们将 \(u'\) 踢出 \(A\) ，然后加入 \(u,v\) ，得到更大的完全子图，导致矛盾。
所以可以选取 \(u'\ne v'\) ，然后考虑 \(uvv'u'\) ，与题设条件矛盾了。
所以选不出 \(u,v\in B\) 不相邻。
一个类似的题目是：若任四个顶点可以找到三个点两两相邻或两两不相邻，那么也可以做这样的顶点集分拆。
例3
设 \(n>4\) ， \(k\) 是整数，满足 \(2\le k\le n-2\) 。图 \(G\) 含 \(n\) 个顶点与至少一条边，证明： \(G\) 是完全图当且仅当任何 \(k\) 个顶点诱导的子图边数相同。
这道题的难度在于条件过强，任何的诱导子图都满足这个条件有些过于强大，我们必须做一些取舍。
法一：
一个自然的观察是我们将会推广结论。
我们先归纳证明结论对任何 \(m\ge k\) 成立。实际上，假设对 \(m\) 成立，每 \(m\) 个点的诱导子图有 \(s\) 条边
那么 \(m+1\) 个点的诱导子图的边数就是 \(\frac {m+1}{m-1}s\) ，因为我们考虑 \(m+1\) 个点诱导子图的每个 \(m\) 个点的诱导子图，共 \(m+1\) 个，而每条边在 \(\binom{m-1}{m-2}=m-1\) 个子图中被统计。
我们只考虑 \(k=n-2,n-1\) ，因为最坏情况我们只有这两个结论。后者给出这是正则图，前者给出 \(n\) 个顶点中任取两个顶点，这 两个顶点之间的边数+两个顶点到剩余 \(n-2\) 个顶点的边数 是不变量（把 \(n-2\) 个顶点的诱导子图的边数扣掉），这个值就是 \(d(u)+d(v)-c\) ，其中 \(c=1\) 当两点相邻， \(c=0\) 当两点不相邻，根据正则图，我们看到 \(c=1\) 对所有 \(u,v\) 成立（不能没有边）
法二：
这个想法的切入点也非常自然，考虑比较简单的 \(k\) 个顶点，比如说，只改变一个顶点。
任取 \(u,v\) 并选 \(k-1\) 个顶点 \(A\) ，考虑 \(A\cup \{u\},A\cup \{v\}\) ，我们看到 \(u,v\) 到 \(A\) 的边数相同。
这对任意 \(u,v,A\) 成立。我们选择 \(u\) 是度数最大的顶点，如果 \(u\) 的度数是 \(n-1\) ，那么它与任何 \(A\) 相邻，给出 \(v\) 也与 \(A\) 相邻，移动 \(A\) 遍历除 \(u,v\) 外的所有点，给出 \(v\) 会与其它所有点相邻，然后给出完全图。
假设 \(u\) 度数不是 \(n-1\) ，任取一个与 \(u\) 的某个邻居 \(w\) 不相邻的 \(v\) （为什么可以这样取？），然后排序其余顶点为 \(w=x_1,x_2,...,x_{n-2}\) ，最前面是与 \(u\) 相邻而与 \(v\) 不相邻的顶点，接着是与 \(u,v\) 均相邻的顶点，最后是与 \(v\) 相邻而不与 \(u\) 相邻的顶点，然后我们看到 \(x_1,x_2,...,x_{k-1}(k-1<n-2)\) 中与 \(u\) 相邻的点一定比 \(v\) 严格多。
这是因为要么 \(x_1,x_2,...,x_{n-2}\) 中与 \(u\) 相邻的点比 \(v\) 严格多，要么相等（ \(u\) 的最大度数），由于 \(x_1\) 是一个与 \(u\) 相邻，与 \(v\) 不相邻的点，如果相等，那么 \(x_{n-2}\) 与 \(v\) 相邻但不与 \(u\) 相邻，问题是 \(k-1<n-2\) 统计不到这个点，导致最后达不到相等，只能是严格小于。
例4
如果一个图的最小度数不小于 \(3\) ，那么存在一个长度不是 \(3\) 的倍数的圈。
有一件事很容易被忽视：我们要说这个图是连通的。否则，考虑其任意一个连通分支。
法一：
我们想要找一个最大圈，然后每个顶点 \(v_i\) 连接了一个子图 \(G_i\) （这里 \(G_i\) 是通过 \(v_i\) 出发遍历（不经过其它 \(v_j\) ）得到的，这样的 \(G_i\) 是不可能重叠的，因为我们从某个点出发如果遍历到了一个之前遍历过的点，那么这个点早该被遍历过了）重要的是 \(G_i,v_j/G_j\) 之间没有边，否则我们可以拓展圈得到更大的圈。然后将中间的圈去掉，考虑剩余子图归纳。
我们需要加强归纳，假设对任何至多两个点度数 \(\le 2\) 的 \(\le n\) 个顶点的图 \(G\) 结论成立，考虑 \(n+1\) 个顶点的图。结论对 \(n=4,5\) 显然成立。
考虑图 \(G\) 的最大圈 \(v_1v_2...v_m\)（显然存在）。如果最大圈内部有一条边，那么可以看到三个圈，这三个一定有一个长度不为 \(3\) 的倍数。所以我们假设圈内部没有边。
那么圈上每个顶点度数均为 \(3\) ，至多两个例外。于是每个点与一个子图 \(G_i\) 连接（ \(G_i\) 连通），每个点至多与 \(G_i\) 中两个点相邻（否则 \(v_i\) 与 \(x,y,z\) 相邻，连通性给出路径 \(xu_1u_2...u_kyr_1r_2...r_lz\) ，然后三个环 \(v_ixu_1...u_kyv_i,v_iyr_1...r_lz,v_ixu_1...u_kyr_1...r_lz\) 必定有一个长度不为 \(3\) 的倍数）
我们声称存在一个 \(G_i\) 不含度数为 \(2\) 的点。实际上因为圈至少有三个点，要么是不存在 \(G_i\) ，即 \(v_i\) 度数为 \(2\) ，要么是 \(G_i\) 含有（至少）一个度数为 \(2\) 的点，因此只能影响两个下标 \(i\) ，
现在考虑这个子图 \(G_i\) ，去掉 \(v_i\) 后至多导致两个点度数 \(\le 2\) ，完成了证明。
法二：
我们可以直接归纳证明原结论。我们还是考虑一个圈，内部没有边，不妨长为 \(3\) 的倍数，然后将这个圈缩为一个点，显然每个点度数还是不小于 \(3\) ，应用归纳假设，找到一个长度不为 \(3\) 的倍数的圈。
如果圈经过了这个点，在复原图形之后，这个圈经过这个点变成了经过这个圈，有两种路径可以选择（ \(v_iv_{i+1}...v_j\) 或者 \(v_iv_{i-1}...v_nv_{n-1}...v_{j+1}v_j\) ），这两条路径长度模 \(3\) 不同余，保证了有一条是安全的。
法三：
考虑最长路径 \(v_0,v_1,...,v_m\) ，考察 \(v_0\) ，它的度数至少为 \(3\) ，然后与 \(v_j,v_k,j,k\ne 1\) 相邻，三个圈 \(v_1...v_jv_1,v_1...v_kv_1,v_1v_jv_{j+1}...v_kv_1\) 一定有一个长度不为 \(3\) 的倍数。
例5
求最小的实数 \(c\) 使得任何 \(n\) 个顶点的图 \(G\) 只要有 \(cn\) 条边，就一定有两个无公共顶点的圈。
得先构造一个图，有较多的边（也即较多的环），但是基本上都有重复的顶点。好的构造是 \(K_{3,n-3}\) ，这说明最优常数 \(c\ge 3\)
我们还是对连通分支证明此问题（用抽屉原理说明一定存在连通分支满足题设）。
我们要用到上一章提到的引理，平均度数 \(\ge 6\) ，我们可以得到一张每个点度数都 \(\ge 4\) 的连通子图。
考虑最长路径 \(v=v_0,v_1,...,v_k=u\)
如果 \(uv\) 不相邻，我们可以考虑 \(v\) 的三个邻居 \(v_{i_1},v_{i_2},v_{i_3}\) 和 \(u\) 的三个邻居 \(v_{j_1},v_{j_2},v_{j_3}\) ，其中 \(i_1<i_2<i_3,j_1<j_2<j_3\)
如果 \(j_3>i_1\) ，我们可以看到 \(vv_1v_2...v_{i_1}v\) 和 \(uv_{k-1}...v_{j_3}u\) 是两个不相交的圈。否则 \(j_3\le i_1\) ，然后 \(vv_{i_2}v_{i_2+1}...v_{i_3}v,uu_{j_1}u{j_1+1}...u_{j_2}u\) 满足条件。
如果 \(uv\) 相邻，我们考察这个圈 \(v_0v_1...v_kv_0\) 内部的边。如果有两条边不“相交”就可以分出两个圈了。我们看如何说明。
我们取度数最大的点 \(v_r\) ，因为平均度数 \(\ge 6\) ，它与至少 \(4\) 个点相邻，不过这里只要用到 \(3\) 个 \(v_i,v_j,v_l,i<j<l\) ，然后考虑 \(v_j\) 某个不同于 \(v_{j-1},v_{j+1},v_r\) 的邻点 \(v_j'\) ，然后（不妨 \(j'<j\) ） \(vjv_j'v_{j'+1}...v_j\) 与 \(v_rv_lv_{l+1}...v_r\) 互不重叠
标签：度数,...,图论,相邻,子图,邻点,基础,概念,顶点 From： https://www.cnblogs.com/Rocking-Yoshi/p/18386476