Given a simple graph with $ 4038 $ vertices. Assume we arbitrarily choose $ 2019 $ vertices as a group (the other $ 2019 $ is another group, of course), there are always $ k $ edges that connect two groups. Find all possible value of $  k $.
1. **Understanding the Problem:**
   We are given a simple graph with \(4038\) vertices. We need to determine the possible values of \(k\), where \(k\) is the number of edges connecting two groups of \(2019\) vertices each.

2. **Initial Observations:**
   - The total number of vertices is \(4038\).
   - We split the vertices into two groups of \(2019\) vertices each.
   - We need to find the number of edges \(k\) that connect vertices between these two groups.

3. **Possible Values of \(k\):**
   - The maximum number of edges between two groups of \(2019\) vertices each is \(2019^2\). This is because each vertex in one group can connect to each vertex in the other group.
   - The minimum number of edges is \(0\) if there are no edges between the two groups.

4. **Lemma and Proof:**
   - **Lemma:** If \((a,b)\) and \((c,d)\) are two disjoint edges, then \(\{a,b,c,d\}\) forms a \(K_4\) (complete graph on 4 vertices).
   - **Proof:** Assume WLOG that \((b,c)\) is not an edge. We create two groups: one containing \(b\) and \(d\), and the other containing \(c\) and \(a\). Let \(X\) be the group containing \(b\) and \(d\), and \(Y\) be the group containing \(c\) and \(a\). Define \(f(v)\) for each vertex \(v\) as the difference between the number of neighbors of \(v\) in \(X\) and \(Y\). We claim that for \(x \in X\) and \(y \in Y\), \(f(y) - f(x) = 2\) if they are connected, and \(0\) otherwise.
     - **Proof of Claim:** Swapping \(x\) and \(y\) does not change the number of edges. Thus, the difference in the number of neighbors remains the same, leading to the conclusion.
     - Back to the lemma: Let \(f(d) = t\). Then \(f(c) = t + 2 \Rightarrow f(b) = t + 2 \Rightarrow f(a) = t + 4\). This implies \(f(a) - f(d)\) cannot be \(0\) or \(2\), contradicting the claim. \(\blacksquare\)

5. **Case Analysis:**
   - **Case 1:** There are no disjoint edges. This implies the graph is a star graph with one vertex connected to all others. In this case, \(k = 2019\).
   - **Case 2:** There exist disjoint edges. We introduce the largest clique:
     - If there is a single vertex outside the largest clique, it must have degree \(0\). This gives \(k = 2019^2 - 2019\).
     - If the graph is a complete bipartite graph \(K_{2019, 2019}\), then \(k = 2019^2\).

6. **Conclusion:**
   The possible values of \(k\) are \(2019\), \(2019^2 - 2019\), and \(2019^2\).

The final answer is \( \boxed{ \{2019, 2019^2 - 2019, 2019^2\} } \).