Connected V-free graph

We claim that the only connected V-free graphs are the complete graphs.

Indeed, suppose there exists two non-adjacent vertices $u, v$ . Since the graph is connected, there is a path $u = v_0, v_1, v_2, \ldots, v_n = v$ . Since the graph is V-free, and $v_0 v_1, v_1 v_2$ are edges, we must have $v_0 v_2$ to be an edge (otherwise $v_0, v_1, v_2$ forms an induced $K_{1,2}$ subgraph). Similarly, since $v_0 v_2, v_2 v_3$ are edges, then $v_0 v_3$ is also an edge. We can induct to reach the conclusion that $v_0 v_n$ is an edge, contradiction.

It's also trivial that complete graphs are V-free (because they don't have any missing edge that's required in a $K_{1,2}$ induced subgraph). There are 2016 complete graphs with no more than 2016 vertices, one for each number of vertices not greater than 2016, so there are also $\boxed{2016}$ connected V-free graphs.

---

Yes, the joke is that we define something that looks interesting, but at the end it just collapses to something trivial. Another example is about spaces equipped with a distance function $d$ satisfying the reverse triangle inequality $d(a,c) \ge d(a,b) + d(b,c)$ .

EDIT a year later: I just knew that a V-free graph is more well-known as a cluster graph .