, 2018

Let $V$ denote the set of all vertices. Let $d$ be the greatest degree of a vertex in the graph and $v \in V$ be a vertex with degree $d$ and let $D \subset V$ be the set of $d$ vertices connected to $v$.

In the full subgraph consisting of vertices in $D$, no vertex can have degree 2 or more, because this would make a cycle of length 4. Therefore, there are at most $\left\lfloor\frac{d}{2}\right\rfloor$ edges in this full subgraph.

Similarly, none of the $7-d$ vertices in $V \setminus (D \cup \{v\})$ can have 2 or more connections to $D$ because this would also make a cycle of length 4. Therefore, there are at most $7-d$ edges between $V \setminus (D \cup \{v\})$ and $D \cup \{v\}$. Finally, the number of edges in $V \setminus (D \cup \{v\})$ is at most $\binom{7-d}{2}$, hence
$$e \leq d + \left\lfloor\frac{d}{2}\right\rfloor + 7 - d + \binom{7-d}{2} = 7 + \left\lfloor\frac{d}{2}\right\rfloor + \binom{7-d}{2}$$
- If $d \geq 5$, $e \leq 7 + \left\lfloor\frac{d}{2}\right\rfloor + \binom{7-d}{2} \leq 10$.
- If $d = 4$, $e \leq 7 + \left\lfloor\frac{4}{2}\right\rfloor + \binom{7-4}{2} = 12$.
- If $d \leq 3$, $e = \frac{\sum_{u \in V} d(u)}{2} \leq \frac{8 \cdot 3}{2} = 12$.

Let us now prove that $e = 12$ is not possible by ruling out the two cases with $d = 4$ and $d = 3$.

1. If $e = 12$ and $d = 4$, then there are exactly 2 edges in the full subgraph consisting of vertices in $D$ (each vertex in $D$ is connected to exactly one other vertex in $D$), there are exactly 3 edges between $V \setminus (D \cup \{v\})$ and $D$ (each vertex in $V \setminus (D \cup \{v\})$ is connected to exactly 1 vertex in $D$) and there are exactly 3 edges in $V \setminus (D \cup \{v\})$ (all 3 of the vertices in $V \setminus (D \cup \{v\})$ are connected).

Let us denote the vertices in $V \setminus (D \cup \{v\})$ by $a_1, a_2, a_3$. $a_i$ and $a_j$ cannot be connected to the same vertex in $D$, otherwise this would make a cycle of length 4 (for example $(a, c, b, x)$ cyclically connected).

Therefore, exactly 3 of the 4 vertices in $D$ are connected to $V \setminus (D \cup \{v\})$. Since each vertex in $D$ is connected to exactly one other vertex in $D$, two of these 3 vertices are connected. Let us call them $x, y$ and let us assume without loss of generality that they are connected to $a_1$ and $a_2$. Now, we have a cycle of length 4 as $(x, y, a_2, a_1)$ are cyclically connected. Therefore, $e = 12$ and $d = 4$ is not possible.

2. If $e = 12$ and $d = 3$, then all vertices in the graph must have degree 3. Let $v$ be any vertex and $D$ be defined as above. Similarly as above, no vertex in $V \setminus (D \cup \{v\})$ can have 2 or more connections to $D$ as this would make a cycle of length 4.

Hence, each vertex in $V \setminus (D \cup \{v\})$ is connected to at most 1 vertex in $D \cup \{v\}$ and thus connected to at least 2 vertices in $V \setminus (D \cup \{v\})$. If we consider the full subgraph consisting of the 4 vertices in $V \setminus (D \cup \{v\})$, each vertex has degree at least 2. In a graph with 4 vertices such that each vertex has degree at least 2, there must be a cycle of length 4. Therefore, $e = 12$ and $d = 3$ is also not possible.

Let us now give an example of a graph with $e = 11$. Consider an octagon $A B C D E F G H$. Now, draw the additional three edges $A C, C E, E G$. This is a graph with 8 vertices, 11 edges and no cycles of length 4.