Problem Description
Let $K_n$ be a complete graph on $n \ge 3$ labelled vertices $v_1, v_2, ..., v_n$. If every edge must be colored either green or red, then how many $N$ distinct ways can the edges be colored such that there exists three vertices $x,y,z$ where $\{ x,y \}$ is green, $\{ y,z \}$ is green, and $\{ x,z \}$ is red?
My Effort Thus Far...
If $k$ is the number of red edges in the graph, then we must have $1 \le k \le {n \choose 2}-2$ in order for three such vertices $x,y,z$ to even exist. I've also determined that three such vertices must always exist whenever $1 \le k < n-1$ (in the interest of space, I will omit the proof). Hence,
$$ N \ge \sum_{k=1}^{n-2} {{n \choose 2} \choose k}$$
Furthermore, when $k=n-1$ there are exactly ${{n \choose 2} \choose n-1} - n$ ways to color the edges so that three such vertices exist. Thus,
$$ N \ge - n + \sum_{k=1}^{n-1} {{n \choose 2} \choose k}$$
For $n-1 < k \le {n \choose 2}-2$, the solution gets tricky because, for any particular $k$, multiple configurations of edge colorings will both rule in and rule out the existence of three such vertices. When examining this by hand for small $n$, I counted the number of graphs in each isomorphism class that allowed three such vertices to exist. Of course, for large $n$ this impractical. I would like to derive some formula that is a function of $n$.
Can anyone $(a)$ help me out, $(b)$ offer potential paths forward, or $(c)$ suggest related theorems or papers to look into? Thanks!