Let $S_{n}$ be a star with $n$ vertices; see Star graph. $S_4$ is called a claw. A claw-free graph is a graph in which no induced subgraph is a claw.
My question is: starting from a star graph $S_n$, what minimum number of edges are added to make the new graph claw-free.
I experimented with small cases, such as $S_4$; it requires adding at least one edge. For $S_5$, we need to add at least two edges, and for $S_6$, at least four edges needs to be added.
P.S. This question can also be transformed into: In a $n$-vertex claw-free graph with maximum degree $n-1$, what is the minimum number of edges it must have?
If you remove the centre vertex, the question becomes how many edges must exist in a graph on $n-1$ vertices so that there’s no independent set of $3$ vertices. The complementary question is how many edges a graph on $n-1$ vertices can have without containing a copy of $K_3$. This is answered by Turán’s theorem, which says that the maximal number of edges is that of the Turán graph, which in this case is $\left\lfloor\frac{(n-1)^2}4\right\rfloor$. Subtracting this from the total number of potential edges, $\binom{n-1}2$, yields
$$ \binom{n-1}2-\left\lfloor\frac{(n-1)^2}4\right\rfloor=\left\lfloor\frac{(n-2)^2}4\right\rfloor\;. $$
You can check that this yields the right result for your small cases.
Here’s another question that was reduced to that question: Covering one part of a bipartite set.