Show that the saturation number sat$(7,C_4) > 7$. A graph $G$ on $n$ vertices is called $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$, but the addition of any edge $e \in K_n \setminus E(G)$ would create a new copy of $H$ in $G$. We define the saturation number sat$(n,H)$ as:
$$\operatorname{sat}(n, H):=\min \{|G|: G \text{ is a $H$-saturated graph on $n$ vertices} \}$$
I want to show that sat$(7,C_4) > 7$. This is equivalent to showing that for any $C_4$-free graph with $7$ vertices and $7$ edges, there exists a non-edge, the addition of which would not create a new $C_4$.
To that end, I let $G$ be a counterexample. $G$ must contain a non-edge $(v_1,v_4)$, as otherwise $G = K_7$ is not $C_4$-free. By the assumption, the addition of $(v_1,v_4)$ in $G$ would create a new $C_4$, which I denote by $v_1 v_2 v_3 v_4 v_1$. But this means $(v_1,v_2)$, $(v_2,v_3)$ and $(v_3,v_4)$ must be already in $G$.
From here I can continue with a case analysis to arrive at a contradiction. But I think there should be another way to do so. Please suggest one.
 A: Consider a counterexample $G$. It must be connected, because otherwise adding an edge between two components would not create any cycle at all. It follows that $G$ is either a tree or a tree plus an additional edge. In the former case you can take a leaf vertex $u$ and a neighbour $v$ of its ancestor that is different from $u$. Then $u$ and $v$ have distance two in the graph and adding an edge between them only creates a triangle.
Thus, we may concentrate on the case when $G$ is a tree plus an edge. Such a graph contains a unique cycle $C_k$, which has length $k=3,5,6$ or $7$. Let's work backwards through these cases. If $k=7$, then $G = C_7$, but this is clearly not $C_4$-saturated. Similarly, if $k=6$, then $G$ is $C_6$ plus a leaf vertex, but $C_6$ itself is not $C_4$-saturated.
The troubles begin with $k=5$, since $C_5$ is $C_4$-saturated! But now we can take a vertex $v$ in $G$ that is not on $C$ but adjacent to some vertex $u$ on $C$. Let $w$ be a neighbour of $u$ on $C$. Then adding the edge $vw$ to the graph creates a triangle and a cycle of length six, but no $C_4$.
The trickiest case is when $k=3$. Our graph is now a triangle $C$ with "branches" (possibly of size zero) hanging off of the vertices of $C$. Since there are seven vertices, there must either be a branch of size at least two, or two branches hanging off of the same vertex. In both cases we can add an edge that only creates a triangle in the graph. (It is cumbersome to describe this in words but if you draw a picture it should be clear.)
This is still whole lot of case analysis. A nice feature of this argument, though, is that it shows why we cannot replace $7$ by $5$ or $6$. Indeed, $C_5$ is $C_4$-saturated with $5$ vertices and edges, and a triangle with a leaf hanging from each vertex is $C_4$-saturated with $6$ vertices and edges. On the other hand, it is not difficult to prove by induction that for $n \geq 7$ we do have $\text{sat}(n,C_4) > n$.
