Lets double count number of pairs of ordered pairs of grups and edge that is between those two groups, or $T=(t_1,t_2,e)$ where $t_1$ and $t_2$ are disjoint groups and $e$ is edge between them. We choose $t_1$ in $\binom{4038}{2019}$ ways and by this we already chose $t_2$. Between them there are exactly $k$ edges so $T= k\binom{4038}{2019}$. Now by counting via edges we get $T=2E\binom{4036}{2018}$ where $E$ is number of edges. Equating we get $2019E=4037k$ So $2019|k$ Now we will prove that $2019|E$ and by this and $4037|E$ we get that graph is empty or complete(which both work) so we would be done. Consider some groups $t_1$ and $t_2$. Name vertices of $t_1$ and $t_2$ as $u_1,...,u_{2019}$ and $v_1,...,v_{2019}$ respectively. Let $x_i$ be degree of $u_i$ in $t_2$ (number of vertices conected with $u_i$ that are in $t_2$) and $y_i$ degree of $u_i$ in $t_1$. Analogously define $z_i$ and $t_i$. Now by moving $u_1$ to $t_2$ and some $v_i$ to $t_1$ (and using $2019|k$) we get $-x_1+y_1-z_i+t_i \equiv 0 \pmod{2019}$ so $x_1+z_i \equiv y_1+t_i \pmod{2019}$ so suming over all $i$ we get $\sum z_i \equiv \sum t_i \pmod{2019}$ but $\sum t_i = \sum y_i=2k \equiv 0 \pmod{2019}$ so we are done by summing everything.

@above $k = 2019$ and $k = 2019^2 - 2019$ both work. For $k = 2019,$ consider a graph in which one vertex connects to all others. The edges connecting the two groups will be exactly the edges connecting this vertex with the 2019 vertices in the other group. For $k = 2019^2 - 2019$ the complement of this graph works.

A hopefully correct solution: $k \in \{2019,2019^{2}-2019,2019^{2} \}$ Lemma: If $(a,b)$ and $(c,d)$ are two disjoint edges, then $\{a,b,c,d \}$ is a $K_{4}$. Proof: WLOG $(b,c)$ is not an edge(all other edges can be obtained by swapping vertices within pairs). Let's make two groups, one of which contains $b$ and $d$, and the other contains $c$ and $a$ (other vertices chosen arbitrarily). Call the group containing $b$ and $d$ group $X$, and the other one $Y$. We introduce $f(v)$ for every vertice $v$ as the difference between the number of neighbours of $v$ amongst the vertices of $X$ and and the vertices of $Y$. We make the following claim. Claim: For $x \in X$ and $y \in Y$, we have $f(y)-f(x)=2$ if the two are connected, and $0$ otherwise. Proof: Simply swap $x$ and $y$. The number of edges remains unchanged. The conclusion follows. $\square$ Back to the lemma: Now let $f(d)=t$. Then we must have $f(c)=t+2 \Rightarrow f(b)=t+2 \Rightarrow f(a)=t+4$. Now it's obvious that $f(a)-f(d)$ can not be neither $0$ or $2$, which contradicts the claim. $\square$ Now we split the problem into two cases based on whether or not there exist two disjoint edges. In the first case, we get that the only possibility is to have a vertex connected to all others as stated above, and in the second case we can introduce the largest clique in order to see there can be either a single vertex outside of it and it has to have degree $0$, in which case we obtain the $k=2019^{2}-2019$ solution or it is a $K_{2019}$.

Solution with p_square and biomathematics. We claim that the only answers are $0, 2019, 2019^2-2019, 2019^2$. Observe that the complete graph, star graph and their conjugates give these values. Let the graph be $G$. Now, for the other cases consider two vertices with different neighbor sets(If we are comparing $v,u$ we do include the opposite vertex regardless of whether its an edge or not). These vertices exist if the graph is not complete or empty. Let these vertices be $u,v$. Let their neighbor sets(we do not include $v$ in $N_u$ and similarly $v$ in $N_v$) be $N_u, N_v$ respectively. Now, let $N=N_u\cap N_v$. Place $u,v$ in opposite groups. Now, place half of $N$ on the side of $v$ and the other half on the side of $u$. Now, consider $N_u\setminus N$ and place as many elements of it on the same side as $v$. Similarly, for $v$, place as many elements of $N_v\setminus N$ on the same side as $u$. Now, replace $u$ and $v$. Now, we cannot comment on whether $uv$ was edge or not but as the total number of elements is conserved and atleast half of the other neighbours of $v$ were on its opposite side, its degree could not have increased, thus it stays same and thus either $u$ neighbours all elements in the entire graph except possibly $v$ or just neighbours $N$. Similarly for $v$. Now, both cannot have all neighbors same by our initial hypothesis, so u just neighbours $N$ and $v$ neighbours $N$ and everything else except possibly $u$. Now, we place as much of $N$ on the side of $v$ and the remaining on side of $u$ and then the remaining vertices arbitrary and do the replacement again. Thus, we get that $N$ is either the empty set or includes everything except $uv$. Now, we get that if $u,v$ have different neighbour sets then either $u$ or $v$ neighbours everything in $G$ and the other neighbours nothing. Now, this directly gives us the existence of atleast one vertex with degree in $(4036,4037)$ and the other in $(0,1)$. Now, if any vertex has degree $4037$ and some other vertex has degree $4036$, we can replace them as before since they have an edge and different neighbour sets, this is impossible. Now, similarly, we cannot have both degree $0$ vertices and degree $1$ vertices. Also, we cannot have both $4037$ and $0$ degree vertices, we get that there are a bunch of universal vertices and a bunch of $1$ degree vertices but if there is any degree $1$ vertex, there can be atmost $1$ universal vertex which gives us the star graph. Now, if there is any $0$ degree vertex, there can be atmost $1$ degree 4036 vertex which gives us the complement of the star graph. Now, if a few vertices have degree $1$ and a few have degree $4036$, we compare any two such which are connected by an edge, then we get a contradiction. Thus, no degree $1$ and degree $4036$ degree vertices are connected but this is impossible as there are an even number of degree $1$ vertices and the $4036$ degree vertex neighbours all except one vertex. Thus, if the graph is not the complete or empty graph, it must be the star graph or its complement.