Solved with franchester, ingenio, GameMaster402, anish9876, mira74, AIME12345, SD2014, AOPS12142015, huangyi_99, sriraamster, kothasuhas, budu, tworigami and mathfun5. In what follows, replace $2019$ by $n$. IT'S OBVIOUS WHY WE SHOULD DO SO. We will apply Engineer's Mathematical Induction on $n$ to show that there are $\ge 2n-5$ edges in each such graph ($n\ge 5$). Establishment of Upper Bound and Preliminaries The partisanship decides unanimously that the base case and constructions for the lower bound are both TRIVIAL by the Fundamental Theorem of Mathematician's Induction. We will call the graphs in the problem PHILLYCHEESESTEAKS. Establishment of Lower Bound Before proceeding with Engineer's Induction Step, the party contends [The Grand Hypothesis] Suppose the statement holds for $n-1$ but not for $n$. Take a PHILLYCHEESESTEAK with $\le 2n-6$ edges. The intuition behind the solution from this point onward is that we will Trust The Process. The heart of the proof lies in the following consideration. Case 1: $\min\deg v = 1$. Suppose $v \sim w$ then $\forall x \not \sim v, w \sim x$, else adding $vx$ will not create triangles, contradiction. Through a tricky application of Kobayashi's Theorem, we obtain that the PHILLYCHEESESTEAK is in fact a tree, but PHILLYCHEESESTEAKS are more tasty than trees, contradiction. $\blacksquare$ Case 2: $\min\deg v = 2$. Suppose $\deg u = 2$ and $u\sim u_1, u_2$. Denote by $\mathcal {U}_i$ the neighborhood of $u_i, i = 1,2$ with $u$ removed. Then $\bigcap_{i=1}^2 \mathcal {U}_i = \emptyset$, else we can delete $u$ and the PHILLYCHEESESTEAK is still a PHILLYCHEESESTEAK, a blatant contradiction to the grand hypothesis in Engineer's Mathematical Induction. The partisanship proceeds to declare that that any crossing edge between $\mathcal{U}_1, \mathcal{U}_2$ must be in the PHILLYCHEESESTEAK and every $ w \ne u_1, u_2, u$ must be in one of $\mathcal{U}_1,\mathcal{U}_2$, from which it follows that there are $|\mathcal{U}_1||\mathcal{U}_2|+n-1 \ge 1(n-4) + n-1 = 2n-5$ edges. Indeed, surely so many brilliant problem solvers cannot ALL be wrong. The following facts are OBVIOUS: $\mathcal{U}_1, \mathcal{U}_2$ are independent components. If $w_1 \in \mathcal{U}_1, w_2 \in \mathcal{U}_2$ are such that $w_1 \not \sim w_2$ then there are no other vertex joining both. Afterwards, the proof follows from Zsigmondy's Theorem. $\blacksquare$ Case 3: $\min \deg v = 3$. Suppose $\deg u = 3$. Proceeding as in the previous case, we obtain a tree structure $u \sim u_1, u_2, u_3$ and each of the other $n-4$ vertices is adjacent to at least one of $u_1, u_2, u_3$. Thus $\sum_{i=1}^3 (d(u_i)-1) \ge n-4$, so that $d(u)+\sum_{i}d(u_i)+\sum_{v \ne u, u_i}d(v) \ge 3+n-4+3+3(n-4)=4n-10$, hence $|E| \ge 2n-5$, a contradiction to the PHILLYCHEESESTEAK having $\le 2n-6$ vertices. $\blacksquare$ Therefore all PHILLYCHEESESTEAKs on $n$ vertices have $\ge 2n-5$ vertices. From the Engineer's Mathematical Induction principle the proof is complete.

Replace $2019$ with $n \geq 5$. The answer is then $2n-5$. For a construction, construct a pentagon with $5$ vertices and edges, and then take the $n-5$ vertices and connect all of them to two non-adjacent vertices of this pentagon. This clearly works. The key idea is the following: the neighborhood of the neighborhood of any vertex must be the entire graph. Therefore, suppose that we have at most $2n-6$ edges. Obviously, $G$ should be connected. If some vertex $v$ with degree $1$ exists, then every other vertex must be adjacent to its sole neighbor $w$. But the no more edges can be added without forming triangles, yet we have $|E|=2018$: contradiction. If there exists some vertex $v$ with degree $2$, let $w_1$ and $w_2$ be its neighbors. Obviously, $w_1$ and $w_2$ are not connected, else we have a triangle. Let the set of vertices adjacent to $w_1$ but not $w_2$ be $A$, the set of vertices adjacent to $w_2$ but not $w_1$ be $B$, and the set of vertices adjacent to both, other than $v$, be $C$. Obviously, no edges exist between vertices in $A \cup C$, as well as vertices in $B \cup C$, else triangles are formed. This immediately implies that if $A$ is nonempty, then $B$ must be as well, else every vertex in $A$ has degree $1$, and likewise if $B$ is nonempty, then $A$ must be as well. Furthermore, if the exist some $u_1 \in A$ and $u_2 \in B$ such that $\overline{u_1u_2}$ is not an edge, then drawing in $\overline{u_1u_2}$ will evidently not form any triangles: contradiction. Therefore, we find that there should be at least $|A||B|+|A|+|B|+2|C|+2$ edges in $G$. Since $|A|+|B|+|C|=n-3$, we have $$|A||B|+|A|+|B|+2|C|+2=|A||B|-|A|-|B|+2n-4=(|A|-1)(|B|-1)+2n-5,$$and since we either have $|A|=|B|=0$ or $|A|,|B| \geq 1$, it follows that there are at least $2n-5$ edges in $G$. If there are no vertices $v$ with degree $2$ (or less), it follows that there exists some vertex $v$ with degree exactly $3$, adjacent to $w_1,w_2,w_3$, since we assumed that $|E|\leq 2n-6<2|V|$. Consider the sum of the degrees of the vertices: every vertex other than $v$ or $w_1,w_2,w_3$ must be adjacent to one of $w_1,w_2,w_3$, contributes a sum of $n-4$ to the degrees of $w_1,w_2,w_3$. Since $v$ is also adjacent to $w_1,w_2,w_3$, a further sum of $3$ is contributed. Finally, both $v$ and the $n-4$ other vertices must have degree at least $3$. Therefore, the sum of degrees is at least $$n-4+3+3(n-3)=4n-10,$$so there must be at least $2n-5$ edges. Since these cases cover all possibilities for the structure of $G$, it follows that we must always have $|E|\geq 2n-5$, as desired. $\blacksquare$

We claim that the answer is $4033$. Let $v_1v_2v_3v_4v_5$ create a cycle with length $5$ and $S=\{v_6,...,v_{2019}\}$. Draw edges between the sets $\{v_2,v_5\}$ and $S$. There are $5+2.2014=4033$ edges in this construction. Suppose that there are at most $4032$ edges. Let $A$ be the vertex with minimum degree (if there exist several vertices, then we choose one of them arbitrarily). If $deg A\geq 4$, then $\frac{4.2019}{2}>4033>E$ which results in a contradiction. Hence we can assume that $deg A\leq 3$. If $deg A=1$, adding an edge between $A$ and any other vertex, there won't exist any triangle so $deg A\geq 2$. Now we split into two cases. Case $I$: If $deg A=2$, let $B,C$ be the friends of $A$ (friendship is equavilent to the existence of edge as usual). Let $T$ be the common friend set of $B$ and $C$ except $A$. Let $S_B,S_C$ be the sets of friends of $B,C$ which are not in $T$ and $A\not \in S_B,S_C$. Note that the minimal distance between any two vertices is at most $2$. In particular, $u$ and $v$ are friends or they have a common friend. Take $u\in S_B, \ v\in S_C$. $u,v$ have no friend in $T$ since $G$ is triangle-free. Also there is no edge in $S_B$ or $S_C$. Since $u,v$ cannot have a common friend in $S_B\cup S_C\cup T$ and $A,B,C$ are not the common friends of them, they don't have a common friend. Thus, $u$ and $v$ must be friends. \[4032\geq E\geq 2+2|T|+|S_B|+|S_C|+|S_B||S_C|=4034+|S_B||S_C|-|S_B|-|S_C|\implies -1\geq (|S_B|-1)(|S_C|-1)\geq 0\]Which is imppossible. Case $II$: If $deg A=3$, let $B,C,D$ be the friends of $A$. $T$ is their common friend set, $K_{BC}$ is the set of common friends of $B,C$ which are not in $T$. Define $K_{BD},K_{CD}$ simultaneously. Let $S_B$ be the friends of $B$ which are not $K_{BC},K_{BD},T$. We also have $A\in S_B,S_C,S_D,K_{CD},K_{BD},K_{BC},T$. Assume that $K_{BC},K_{BD},K_{CD}\geq 1$. Vertices from $S_B$ and $K_{CD}$ cannot have common friend in $S_C,S_D,K_{BD},K_{BC},T$ and $A,B,C,D$ are not their common friends hence they cannot have a common friend. This implies any vertex in $S_B$ is friend with any vertex in $K_{CD}$. \[4032\geq E\geq S_BK_{CD}+S_CK_{BD}+S_DK_{BC}+3T+3+S_B+S_C+S_D+2K_{CD}+2K_{BD}+2K_{BC}\]\[\geq (S_B+S_C+S_D+K_{CD}+K_{BD}+K_{BC}+T+3)+T+(T+K_{CD}+K_{BD}+K_{BC}+S_B+S_C+S_D)\]\[\geq 2019+2016+T=4035\]Which is not correct. Now consider the case where at least one of $K_{CD},K_{BD},K_{BC}$ is equal to $0$, WLOG $K_{BC}=0$. If $K_{BD}=0$, then $D$ and $S_C$ cannot have a common friend hence $K_{BD},K_{BC}\geq 1$. Since each vertex in $S_B$ in graph $S_B\cup S_C\cup S_D$ have positive degree and $S_B$ has no edge inside itself, there are at least $S_b$ edges in $S_B\cup S_C\cup S_D$. \[4032\geq E\geq 3+3T+S_B+S_C+S_D+2K_{BD}+2K_{BC}+S_B+S_CK_{BD}+S_DK_{BC}\]\[\geq (3+T+S_B+S_C+S_D+K_{BD}+K_{BC})+K_{BD}+K_{BC}+S_B+S_CK_{BD}+S_DK_{BC}+2T\]\[2019+K_{BD}+K_{BC}+S_B+S_CK_{BD}+S_DK_{BC}+T+(2018-S_B-S_C-S_D-K_{BD}-K_{BC})>4034\]As desired.$\blacksquare$