Let G be a simple graph of even order n having a set S of size k such that o(G-S) > k. Prove that G has at most $\binom{k}{2} + k(n-k) + \binom{n-2k-1}{2}$ edges, and that this bound is best possible. Use this to determine the maximum size of a simple $n$

문제출처

광주과학기술원 GIST 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 7

---

Solution

1. The total number of edges in $G$ can be expressed as:
$$
|E(G)| = e(G[S]) + |[S, \bar{S}]| + e(G[\bar{S}]),
$$
where $e(G[S])$ is the number of edges within $S$, $|[S, \bar{S}]|$ is the number of edges between $S$ and $\bar{S}$, and $e(G[\bar{S}])$ is the number of edges within $\bar{S}$.

2. Since the size of $S$ is $k$, we have:
$$
e(G[S]) \leq \binom{k}{2}.
$$
Equality holds if and only if $S$ forms a complete graph.

3. $S$ has $k$ vertices, and $\bar{S}$ has $n-k$ vertices. Thus:
$$
|[S, \bar{S}]| \leq k(n-k).
$$
Equality holds if and only if $S$ and $\bar{S}$ form a complete bipartite graph.

4. Since $o(G-S) > k$, $G-S$ has at least $k+1$ odd components. Therefore, the number of remaining vertices is $n-k-(k+1) = n-2k-1$. Thus:
$$
e(G[\bar{S}]) \leq \binom{n-2k-1}{2}.
$$
Equality holds if and only if $\bar{S}$ forms a complete graph on $n-2k-1$ vertices.

5. Combining these results, we have:
$$
|E(G)| = e(G[S]) + |[S, \bar{S}]| + e(G[\bar{S}]) \leq \binom{k}{2} + k(n-k) + \binom{n-2k-1}{2}.
$$
Equality holds if $G$ is constructed by complete graphs $S$, $\bar{S}$, and $S$ and $\bar{S}$ form a complete bipartite graph. This guarantees that the equality represents an upper bound.

6. To prove that this upper bound is best possible, we construct a graph that satisfies the equality condition:

1. Construct $S = K_k$. Thus, $e(G[S]) = \binom{k}{2}$.
2. Construct $\bar{S} = K_{n-2k-1}$. Thus, $e(G[\bar{S}]) = \binom{n-2k-1}{2}$.
3. $S$ and $\bar{S}$ are disjoint subsets of $V(G)$. Add every possible edge between $S$ and $\bar{S}$. Since $S$ contains $k$ vertices and $\bar{S}$ contains $n-k$ vertices, we have $|[S, \bar{S}]| = k(n-k)$.
4. Therefore, a graph satisfying the upper bound exists, and it is the best possible construction.

7. This result holds under the given condition $o(G-S) > k$. Since $|S| = k$, this implies $o(G-S) > |S|$, which is the lower bound for the no 1-factor condition (the opposite of Tutte's condition).

8. Therefore, the maximum size of a simple $n$-vertex graph with no 1-factor is:
$$
|E(G)| = \binom{k}{2} + k(n-k) + \binom{n-2k-1}{2}.
$$