In a simple graph $G$, we call $t$ pairwise adjacent vertices a $t$-clique. If a vertex is connected with all other vertices in the graph, we call it a central vertex. Given are two integers $n,k$ such that $\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n$. Let $G$ be a graph on $n$ vertices such that (1) $G$ does not contain a $(k+1)$-clique; (2) if we add an arbitrary edge to $G$, that creates a $(k+1)$-clique. Find the least possible number of central vertices in $G$.
Problem
Source: 2012 China TST Test 2 p1
Tags: algorithm, induction, combinatorics proposed, combinatorics
19.03.2012 17:46
We call the simple complete $k$-partite graph on $n$ vertices in which all parts are as equal in size as possible is called a Turan graph and denoted ${T_{k,n}}$. ${T_{k,n}}$ has $2k - n$ central vertices, and add an arbitrary edge to ${T_{k,n}}$ will creates a $(k + 1)$-clique.
19.03.2012 22:09
Not all edge-maximal graphs with no $k$-clique are TurĂ¡n graphs ...
20.06.2012 02:50
To show that when $k+1\le n\le 2k-1$, there are at least $2k-n$ central vertices, we use the following algorithm to gradually build up the set of central vertices: 0. Since $n\ge k+1$, some two vertices $u,v\in G$ are non-adjacent; let $T=\{u,v\}$, $S$ be some $K_{k-1}$ clique adjacent to $u,v$, and $U=G\setminus\{T,S\}$. Note that $|S|=k-1=2k-n+|U|$. 1. Suppose we have pairwise disjoint sets $T,S,U$ such that $G=T\cup S\cup U$, $T\cup S\subseteq N(S)$, and $|S|\ge 2k-n+|U|$ (clearly $S$ must be nonempty). If $U=\emptyset$, then $S$ is a set of at least $2k-n$ central vertices, so we're done. Otherwise, choose an arbitrary vertex $u\in U$. 2. If $S\subseteq N(u)$, then go back to step 1 with $U'=U\setminus\{u\}$, $T'=T\cup\{u\}$, and $S'=S$; clearly $|S'|\ge 2k-n+|U'|$. Otherwise, pick a vertex $v\in S$ such that $u,v$ are non-adjacent. 3. By condition (2), there exists some $K_{k-1}$ adjacent to $u,v$ composed of the sets $U_0\subseteq U\setminus\{u\}$, $T_0\subseteq T$, and $S_0\subseteq S\setminus\{v\}$. But $G$ contains no $K_{k+1}$, so $|T_0|+|S|\le k$, whence \begin{align*} k-1 = |U_0|+|T_0|+|S_0| &\le |U_0|+k-|S|+|S_0|\\ \implies |S_0|\ge -|U_0|+|S|-1&\ge 2k-n+(|U|-|U_0|-1). \end{align*}Since $|U_0|\le |U|-1$, $S_0$ must be nonempty. Thus we can go back to step 1 with $U'=U\setminus(\{u\}\cup U_0)$, $T'=T\cup\{u\}\cup U_0\cup(S'\setminus S_0)$, and $S'=S_0$. Because the number of vertices in $U$ decreases after each iteration, this algorithm terminates, so we're done.
20.01.2014 05:14
Here's another solution (hopefully its not similar to above): The answer is $2k-n$. We can rephrase the problem as follows with by taking the complement of our original graph: if a graph $G$ has $m$ vertices of degree $0$ has an independent set of size $\alpha$, but when you delete any edge of it, we get an independent set of size $\alpha+1$, then $|G| \ge 2 \alpha - m$. We can prove this by induction. So it's clear that we can assume that $G$ has no vertices of degree 0, or else delete them and induct. We can also assume that $G$ is connected, or else induct on components. Say that $A$ is an independent set in $G$, and $|A| = \alpha$. Take a vertex $v \in A$. Now let $v$ has $p(v)$ neighbors who have degree $1$, and call the set of these neighbors $P$. Now note that the $A+P-v$ is an independent set. So $p(v) \le 1$ by maximality. Now look at the graph $G' = G-v$. If $p(v) = 1$, $G'$ has an independent set of size at least $\alpha - 1 + p(v) = \alpha$. And exactly 1 vertex has degree 0. So $|G'| \ge 2\alpha - 1$. So $|G| = |G'|+1 \ge 2\alpha$. Now, say $p(v) = 0$. If $G$ had 2 or more maximal independent sets, we could choose $v$ to not be in at least one of them, so we would be done by induction, because if we delete $v$ to get a new graph $G'$, then since $G'$ still has an independent set of size $\alpha$, $|G'| \ge 2\alpha$ by induction (since it has no vertices of degree 0, since $p(v) = 0$), so $|G| = |G'|+1 \ge 2\alpha+1$. Now assume $G$ has only $1$ independent set. Let $A$ be this independent set, and let $B$ be the other vertices. Then each vertex in $B$ is adjacent to at least one vertex in $A$, by maximality. But if some vertex $v \in B$ is adjacent to both $x, y$ in $A$, then deleting the edge $vx$ won't increase the maximum independence set, contradiction. So each vertex in $B$ is adjacent to exactly one vertex in $A$. By connectivity, each vertex in $A$ is adjacent to at least one vertex in $B$, so $|B| \ge |A|$. So $|G| = |B|+|A| \ge 2|A| = 2 \alpha$.
06.04.2015 18:14
My proof closely models the cloning proof of Turan's Theorem (except without cloning). I claim that the answer is $ \boxed{2k - n} $ - this can be obtained by considering the Turan graph $ T_{n, k}. $ Consider the graph with the minimal number of central vertices. I claim that there do not exist three vertices $ u, v, w $ in the graph such that $ v $ is adjacent to $ w $ and $ u $ is not adjacent to $ v $ and not adjacent to $ w. $ Assume for the sake of contradiction that three such vertices do exist. Now consider a central vertex $ a. $ I claim that any $ k + 1 $-clique that exists after an edge is added between vertices $ u $ and $ v $ contains $ a. $ Assume the contrary - then there is a $ k - 1 $-clique all of whose vertices are connected to $ u $ and $ v $ none of whose vertices are $ a. $ But then the vertices of that $ k - 1 $-clique and $ a $ and $ u $ form a $ k + 1 $-clique, contradiction. Now, delete the edge between $ a $ and $ v $ and add an edge between $ v $ and $ u. $ I claim that this new graph satisfies all the properties outlined in the problem and has fewer central vertices than the graph we started with. Since $ a $ is no longer a central vertex and since clearly no vertex became a new central vertex in the new graph, it suffices to check that the new graph contains no $ k + 1 $-clique and adding any edge to the new graph results in a graph with a $ k + 1 $-clique. Since all $ k + 1 $-cliques formed by adding an edge between $ u $ and $ v $ contained $ a $ and we deleted the edge between $ a $ and $ v, $ we know that the new graph contains no $ k + 1 $-clique. Also if we add an edge between $ a $ and $ v $ in the new graph, we obtain the same graph as if we had added an edge between $ u $ and $ v $ in the original graph, which by definition yields a graph containing a $ k + 1 $-clique. Therefore the new graph contradicts the minimality of our original graph. This means that "not being adjacent" is an equivalence relation between vertices which means that our graph is complete and partite. Since it must be at least $ k $-partite, we easily obtain the desired result.
08.04.2015 01:39
@above: But how do you prove there are not $0$ central vertices?
26.09.2021 14:18
We see that our graph is just isomorphic to $T(k,n)$. So,the number of central vertices are just a single element set of the k-partition. And hence ,they are atleast $2k-n$ as $k$ is in the desired range. In fact,they are exactly these many central vertices.