For a complete graph on n verticies, what is the minimum number of edges which must be removed in order to eliminate all 4-cycles?

Question

Let n be a natural number. For a complete undirected graph, G, on n vertices, what is the minimum number of edges which must be removed from G in order to eliminate all cycles containing 4 edges?

---

Another user told me that I am not allowed to ask a question on stack exchange unless I first attempt to answer the question. The same person says that I must provide my attempted answer inside of the question description. However, I think it would make more sense to post an attempted answer as an answer. My attempted answer might be wrong, or only partially complete, but stack exchange answers often are. If you think I'm cheating on homework assignment without ever even trying to answer the question, then you're mistaken. I have posted my best approximation of an answer.

Answer 1

The complementary problem of finding the maximum number of edges in a graph on $n$ vertices with no 4-cycle is OEIS sequence A006855. So your sequence is $\binom{n}{2} - \text{A006855}(n)$.

Answer 2

For any natural numbers $a$ and $b$ let ${}_{a}P_{b} $ be the number of length $b$ permutations taken from a set of size $a$.

Let $K_n$ be a complete graph on $n$ vertices.

Let $ES(K_n)$ denote the edge set of Kn.

Let $CS(K_n)$ denote the set of all 4-cycles in $Kn$

Let Φ be a mapping from the power set of $ES(K_n)$ to the power set of $CS(K_n)$ such that:

For any set of edges, $ES$, for any edge $E$ in $ES$, for any cycle $C$ in $CS(K_n)$, $C$ is in the set $Φ(ES)$ if and only $E$ is in cycle $C$.

For example, suppose that $e_1$, $e_2$, $e_3$ are edges in graph $K_n$.

Then Φ{$e_1$, $e_2$, $e_3$} is the set of all 4-cycles containing edge $e_1$, or containing $e_2$, or edge $e_3$.

Suppose that we choose $1$ edge in the complete graph and remove it. How many 4-cycles have just been removed as a result?

Let $v$ and $w$ be distinct vertices in graph $K_n$

$|Φ\{v, w\}|$ is the number of 4-cycles containing edge $\{v, w\}$

This is equivalent to the number of paths containing 4 nodes and starting at vertex $v$ and ending at vertex $w$. Since the first and last vertex of the path are fixed, we need only consider the two vertices which appear in the middle of the path.
|Φ{$v, w$}|$ = {}_{n-2}P_{2}$

Suppose that we choose 2 edges, $e_1$ and $e_2$, in the complete graph to remove.
How many 4-cycles have just been removed as a result?

By the inclusion-exclusion principle,
|Φ{$e_1$) ∪ $e_2$}| = |Φ{$e_1$}| + |Φ{$e_2$}| – |Φ{$e_1, e_2$}|

Suppose edges $e_1$ and $e_2$ are incident to each other. Consider the set of 4-cycles containing both edges. Three vertices in the cycle are already fixed, and only one vertex remains to be chosen.
|Φ{$e_1, e_2$}| = $n-3$ if edge $e_1$ incident to $e_2$.

Suppose edges $e_1$ and $e_2$ are NOT incident to each other. Then,
|Φ{$e_1, e_2$}| $= 2$

We want to eliminate as many cycles as possible while removing as few edges as possible. As such, for 2 edges, it is prudent to choose edges which are NOT incident to each other.
|Φ{$e_1$) ∪ Φ ($e_2$}| = |Φ{$e_1$}| + |Φ{$e_2$}| – |Φ{$e_1, e_2$}|
|Φ{$e_1$}| = |Φ{$e_2$}| = ${}_{n-2}P_{2}$
|Φ{$e_1, e_2$}| = 2 '

Thus, |Φ{$e_1$) ∪ Φ ($e_2$)}| = $2*{}_{n-2}P_{2} - 2$

We are done with 1 edge and 2 edges. What about 3 or more edges?
Suppose we have $k >= 3$ disjoint edges.
Then, Φ{$e_1, e_2, …, e_k$} is the empty set. That is, no 4-cycle contains 3 or more disjoint edges.
|Φ($e_1$) ∪ Φ($e_2$) ∪ … ∪ Φ($e_k$)| = $k*{}_{n-2}P_{2} – \binom{k}{2}* 2$
If the edges are not disjoint, then Φ($e_1, e_2, e_3$) might not be the empty set.
However, I conjecture for sufficiently large $n$, that the terms relating two edges outweigh the terms relating 3 or more edges.
$(-1)*( \text{many copies of } n - 3) + (+1)*( \text{some small stuff}) < (-1)*( \text{many copies of } 2) + (+1)*( \text{zero})$.
We would like to know when the set of 4-cycles covered by some set of edges is exactly equal to set of all 4-cycles in the graph.
There are $3*\binom{n}{4}$ distinct 4-cycles in the graph
There are $k*{}_{n-2}P_{2} – \binom{k}{2}* 2$ 4-cycles broken by eliminating $k$ pairwise non-incident edges.
$k*{}_{n-2}P_{2} – \binom{k}{2}* 2 = 3*\binom{n}{4}$
If there are $n$ nodes, then I think we must remove at least... $ 1/4 (14 - 10 n + 2 n^2 - sqrt(2) sqrt(98 - 134 n + 67 n^2 - 14 n^3 + n^4))$
edges in order to eliminate all of the 4-cycles.

It looks like approximately $0.14645*n^{2}$ edges must be removed.