Hmm can you clarify the "100-rank simple graph"?

I infer it as a $100$-regular graph.

The original text is "100 阶图" which means "graph with order 100" (see first term here), so I think it should be a graph with 100 vertices (not a 100-regular graph).

Here is a solution with help from adamov1 and msinghal. Hopefully there are no mistakes. Consider the graph $H$ on the 100 vertices where we connect two vertices $u$ and $v$ if in $G$, $u$ and $v$ are connected and $N(u)\cap N(v)=\emptyset$. The condition tells us that there are no isolated vertices in $H$. First, we partition the vertices into groups $A_1,A_2,\ldots,A_k$ so that the $H$-induced subgraphs on $A_i$ is a star graph for all $i$. This is easy to do by the following algorithm: If there are no vertices of degree 1, then remove any two connected vertices and put them in a group. Otherwise, take a vertex $u$ of degree 1 and look at the sole vertex $v$ it is connected to. Remove $v$ and all vertices of degree 1 it is connected to and put them in a group. Now suppose we have our groups $A_1,A_2,\ldots,A_k$, and let the vertex in $A_i$ that does not have degree 1 be $v_i$ (if $|A_i|=2$, let either vertex be $v_i$). Let $|A_i|=x_i+1$ for all $i$, so $x_i$ is the number of vertices in degree 1 (different from $v_i$ if $|A_i|=2$) in $A_i$. The key claim here is that there are at most $x_ix_j+1$ edges between $A_i$ and $A_j$ for any $i,j$. Indeed, note that if $u\in A_i$, $u\ne v_i$, and $u$ is connected to $v_j$, then $u$ cannot be connected to any other vertex $w$ in $A_j$. This is because otherwise, $u\in N(v_j)\cap N(w)$, a contradiction. Now, if $u$ is connected to $v_j$, then replace the edge between $u$ and $v_j$ with edges between $u$ and the rest of the vertices in $A_j$. This does not decrease the number of edges between $A_i$ and $A_j$. At the end, $v_i$ and $v_j$ can only be adjacent to each other. The other edges form a subgraph of the $K_{a_i,a_j}$ between $A_i\setminus\{v_i\}$ and $A_j\{\setminus v_j\}$, so the claim is proven. Also, within $A_i$ there are exactly $x_i$ edges. Indeed, $v_i$ is connected to the rest of the vertices in $A_i$ and if $u_1,u_2\in A_i$ are connected with $u_1,u_2\ne v_i$, then $u_1\in N(v_i)\cap N(u_2)$, a contradiction. Summing over all $A_i$ and $A_i,A_j$ gives that there are at most $\binom k2+\sum_{1\le i<j\le k} x_ix_j+\sum_{1\le i\le k} x_i$ edges. This is achievable by taking drawing an edge between $v_i,v_j$ for all $i,j$, $v_i$ and the rest of the vertices in $A_i$ for all $i$, and a $K_{x_1,x_2,\ldots,x_k}$ on $A_1\setminus\{v_1\},A_2\setminus\{v_2\},\ldots,A_k\setminus\{v_k\}$. It is easy to check that this graph satisfies the conditions. Hence, we want to maximize $\binom k2+100-k+\binom{100-k}2-\sum_{i=1}^k\binom{x_k}2$ over all positive integers $k,x_1,x_2,\ldots,x_k$ with $x_1+x_2+\cdots+x_k=100-k$. Now I leave the computation to adamov1:

Note that if we let the $x_i$ instead be positive reals, then this function is at most \[f(k)=\binom{k}{2}+100-k+\binom{100-k}{2}-k\binom{\frac{100}{k}-1}{2}\]by the convexity of $\binom{x}{2}$. It is not difficult to see that this is increasing on $k\le 7$ and decreasing on $9\le k\le 50$, and furthermore we know that $f(7)=\frac{26745}{7}<3822$ and $f(9)=\frac{34267}{9}<3822$. So if $k\not=8$, the number of edges is less than $3822$. Now note that if $k=8$, we would like to minimize the expression $\sum_{i=1}^8 \binom{x_i}{2}$ subject to $x_1+...+x_8=92$. Again by convexity, this is minimized at $(x_1,...,x_8)=(12,12,12,12,11,11,11,11)$ (and permutations), so the maximum of the given expression for $k=8$ is $\binom{8}{2}+92+\binom{92}{2}-4\binom{12}{2}-4\binom{11}{2}=3822$, which is greater than the possible values for $k\not=8$ and thus the answer is $3822$. What a nice answer! (The equality case is a $K_{12,12,12,12,11,11,11,11}$ (colored with 8 colors) along with a $K_8$ such that each element of the $K_8$ is connected to all the elements of a distinct color.)

We claim the answer is $\boxed{3822}$. We will describe the equality case after proving the bound. Call an edge good if it is not part of any triangles. The problem condition is equivalent to the statement that every vertex is incident to some good edge. Consider a minimal set $S$ of good edges such that every vertex is incident to some edge in $S$. We claim that $S$ is a collection of disjoint star graphs. Indeed, there are no cycles in $S$, as removing one edge in that cycle from $S$ is a smaller valid set, and similarly there are no paths of length $3$ or more, since removing a middle edge from the path is also a valid set. Suppose the stars in $S$ have sizes $a_1,\ldots,a_m$, where a star of size $a$ is a vertex connected to $a$ leaves. In particular, we have that \[\sum_{i=1}^m (a_i+1)=100.\]Note that we can't add any edges within the vertices of any given star, since that would create a triangle involving some edge of the star. We now have the following key estimate. Lemma: Suppose we have two stars of sizes $a$ and $b$. We add a set $E$ of edges between them such that none of the edges of the stars is part of a triangle. Then, $|E|\le ab+1$. Proof: Suppose $\alpha$ is the root of the $a$-star and $x$ is some leaf of the $a$-star. Let $d_a$ be the number of edges of $E$ incident to $\alpha$, and let $d_x$ be the number of edges of $E$ incident to $x$. We claim that \[\frac{1}{a}d_a+d_x\le b+\frac{1}{a},\]and summing this over all leaves $x$ finishes. Indeed, each vertex in the $b$-star can be connected to only one of $a$ or $x$, so $d_a+d_x\le b+1$. However, $x$ cannot be connected to both the root and a leaf of the $b$-star, so $d_x\le b$. Thus, \[\frac{1}{a}d_a+d_x\le \frac{1}{a}(b+1)+\frac{a-1}{a}b=b+\frac{1}{a},\]as desired. $\blacksquare$ Thus, the total number of edges is at most \[\sum_{i=1}^m a_i+\sum_{1\le i<j\le m}(1+a_ia_j).\]Letting $b_i=a_i+1$, we see after much omitted computation that the number of edges is at most \[\frac{100^2}{2}-(100-m)(m-2)-\frac{1}{2}\sum_{i=1}^m b_i^2.\]It suffices now to show that the maximum of the above expression over all sequences $(b_1,\ldots,b_m)$ that sum to $100$ and have $b_i\ge 2$ is $3822$. Since $b_i\ge 2$ for all $i$, we have $1\le m\le 50$. By Cauchy-Schwarz, we have \[\sum_{i=1}^m b_i^2\ge\frac{100^2}{m},\]so \[\frac{100^2}{2}-(100-m)(m-2)-\frac{1}{2}\sum_{i=1}^m b_i^2\le \frac{100^2}{2}-(100-m)(m-2)-\frac{1}{2}\frac{100^2}{m}.\]It is ``not hard'' to see that \[f(m):=\frac{100^2}{2}-(100-m)(m-2)-\frac{1}{2}\frac{100^2}{m}<3822\]for $m\in[1,50]\setminus\{8\}$. We see $f(8)=3823$, so if there is a graph with more than $3822$ edges, then equality is achieved for our CS bound, so all the $b_i$ are equal to $100/8$, which is not an integer. Therefore, we have \[\frac{100^2}{2}-(100-m)(m-2)-\frac{1}{2}\sum_{i=1}^m b_i^2\le 3822,\]as desired. As a side note, equality is achieved at $(b_1,\ldots,b_8)=(12,12,12,12,13,13,13,13)$, which motivates the equality case. The equality case is four $11$-stars and four $12$-stars, with all the roots of the stars connected to each other, and the $8$ groups of sizes $(11,11,11,11,12,12,12,12)$ connected to make the complete $8$-partite graph $K_{11,11,11,11,12,12,12,12}$. >>>

若 ${G}$ 中的某一条边 ${e}$ 不在任何三角形中, 则称 ${e}$ 为一条好边. $G(V$,$E)$ 中, $\forall X\in V(G)$, ${X}$ 引出了至少一条好边, 即只需求出 $f=|E(G)|$ 的最大值. 对于 ${X}$, ${Y}\in V(G)$, 若 $XY$ 连边, 且 $d(X)$, $d(Y)\geq 2$, 去掉边 $XY$, 仍然无孤立点. 一直进行下去, 会得到若干个星图, 此时无法再去边. 设有 ${m}$ 个星图, 分别有 $n_1$, $n_2$, $\cdots$, $n_m$ 个点. 则 $\sum\limits_{i=1}^mn_i=100$. 对有 $n_i$ 个点的星图, 以一点为中心引出了 $n_i-1$ 个点. 去进行加边, 即只需求出最多可加边数 ${f}$. 考虑对于 $\forall 1\leq i<j\leq n$, 看有 $n_i$, $n_j$ 个点的 ${2}$ 个星图 $U$ 连 $U_1$ 至 $U{n_i-1}$, 以及 $V$ 连 $V_1$ 至$V{n_j-1}$.考虑最多可加边数. 若 $UV$ 相连, 且 $U$ 不连 $V_1$ 至$V{n_j-1}$, ${V}$ 不连 $U_1$ 至 $U{n_i-1}$. 则可加边至多为 $(n_i-1)(n_j-1)+1$. 若 $UV$ 不连, 设 $U$ 连了 ${x}$ 个 $V_1$ 至$V{n_j-1}$ 中的点, $V$ 连了 ${y}$ 个 $U_1$ 至$U{n_i-1}$ 中的点. 则所加边至多为 $$\begin{aligned}x+y+(n_i-y-1)(n_j-x-1)&=(n_i-1)+(n_j-1)+(n_i-y-2)(n_j-x-2)-1\\&\leqslant (n_i-1)+(n_j-1)+(n_i-2)(n_j-2)-1+1\\&=(n_i-1)(n_j-1)+1.\end{aligned}$$因此可以得到 $$\begin{aligned}f &\leqslant\sum\limits_{i=1}^m(n_i-1)+\sum\limits_{1\leq i<j\leq m}\left( (n_i-1)(n_j-1)+1\right)\\ &=100-m+\sum\limits_{i=1}^m(n_i-1)+\sum\limits_{1\leq i<j\leq m}\left( n_in_j-n_i-n_j+2\right)\\ &=100-m+2\dbinom{m}{2}-(m-1)\sum\limits_{i=1}^mn_i+\sum\limits_{1\leq i<j\leq m}n_in_j\\ &=100-m+m^2-m-100(m-1)+\frac 12\left(\left(\sum\limits_{i=1}^mn_i\right)^2-\sum\limits_{i=1}^mn_i^2\right)\\ &=m^2-102m+200+\frac{100^2}2-\frac 12\sum\limits_{i=1}^mn_i^2\\ &=m^2-102m+5200-\frac 12\sum\limits_{i=1}^mn_i^2\\ &\leqslant m^2-102m+5200-\frac 1{2m}\left(\sum\limits_{i=1}^mn_i\right)^2\\ &=m^2-102m+5200-\frac{5000}{m}.\end{aligned}$$由 $f'=2m-102+\frac{5000}{m^2}$. 令 $f'=0$, 知 $m=8$ 为正整数时可取得最小值, 故 $f\leqslant 3823$. 若 $f=3823$, 则 $m=8$ 且 $n_1=n_2=\cdots =n_8=\frac{100}8\notin\mathbb Z_+$, 矛盾. 故 $f\leqslant 3822$. 取 $m=8$, 让 $n_1=n_2=n_3=n_4=13$, $n_5=n_6=n_7=n_8=12$, 可取得 $3822$. 故所求最大值为 $\boxed{3822}$.$\blacksquare$

This is a nice problem, probably one of my favorites. Looking back on what i've typed, it's actually a decently easy problem, maybe 25 mohs! the annoying part was the algebra \textit{Setup (boring trivial):} The answer is 3822, with construction as four $11$-stars and four $12$-stars, with all the roots of the stars connected to each other, and the $8$ groups of points of sizes $(11,11,11,11,12,12,12,12)$ connected pairwise. We rephrase the problem to a graph $G'$ with $E(V)=\{(u,v):N(u)\cap N(v)=\emptyset\}$: The statement tells us that it's a forest, but we can group in stars as follows: for $v:\text{deg}(v)=1$ connected to u, simply take u as the center and the other deg 1 vertices connected to it as the star; otherwise since it's easy to deduce there's no triangle we may remove two connected vertices and put them together (since if u,v are removed, and w was deg 2, it can't be connected to both u and v). Furthermore, let $v_i\in S_i$ be the center of the star (for $|S_i|=2$ anything), with $a_i=|S_i|-1$ the number of ``points'' (deg. 1s). \begin{claim*} [Actual work but still trivial] Between any two stars $S_i,S_j$ there are at most $x_ix_j+1$ edges for all $i\ne j$. So there are at most $\tbinom k2+\sum_{1\le i<j\le k}a_ia_j+\sum_{1\le i\le k}a_i$ edges. \end{claim*} \begin{proof} Obvious: Follows from $w_i\in S_i$ is either only connected to $v_j\in S_j$ (by no triangles) or connected to the other $a_j$ vertices; the maximum (!!) would then be when the $w_i,w_j$ are connected pairwise and $v_i$ connected to $v_j$. \end{proof} So we'd like to maximize $$\tbinom k2+\tfrac12(\sum_ia_i)^2 - \sum_ia_i^2 + \sum_i a_i = \tbinom k2 +\tfrac12((100-k)^2 - \sum_i a_i^2) + (100-k) =\tfrac12((2k^2-203k) - \sum a_i^2) + 5100;$$we obviously know by smoothing it happens when the $a_i$ are close to each other, so trying each of the values we see that k=8 is best. Nice!

Was it really necessary to choose $n = 100$? Why not choose $n = 1984$ so the answer extract is easier? Not that hard but wow what a scary problem statement. Claim: Let $a_1 + a_2 + \dots + a_{n} = 100 - n$. Then \[ \frac{1}{2} \cdot \left((100-n)^2 - \sum_{i=1}^n a_i^2\right) + \frac{n(n-1)}{2} + 100 - n \le 3822 \]with equality when $n = 8$ with four occurences of $a_i = 11$ and four occurences of $a_i = 12$. Proof. Note that for fixed $n$ the bound is tightest when $|a_i - a_j| \le 1$ over all $i, j$, which is unique for each $n$, and thus this is maximal for $n = 8$. Then we can verify that \[ f(n) = \frac{1}{2} \cdot \left((100-n)^2 - n \left(\frac{100-n}{n}\right)^2\right) + \frac{n(n-1)}{2} + 100 - n \]is at least the right hand side, and $f'(n)$ is zero at $n = \frac{1}{2} \pm \frac{\sqrt{201}}{{2}}, 50$ where $50$ is a local maximum and the other two are negative / minimum. As such, it remains to verify that $f(n) \le 3822$ for $n = 7, 9$ which can be done and suffices. $\blacksquare$ This gives our construction of taking four stars with $11$ leafs, four stars with $12$ leafs, and connecting every two leafs and every two star centers. Conversely, given any graph $G$, consider the induced subgraph $G'$ consisting of any edge $u, v$ where $u$ and $v$ don't have any common neighbors but are neighbors. Then we can take a subgraph of $G'$ by repeatedly removing any edge where both $u, v$ have degree at least $2$ to get a subgraph of $G'$ which consists of some star graphs $S_1, S_2, \dots, S_n$ with $a_1, a_2, \dots, a_n$ leaves respectivley. We can then show that the max number of edges connecting $S_i$ and $S_j$ is $a_i \cdot a_j + 1$ by noting that if the center vertex $c_i$ of $S_i$ is connected to any leaf $\ell \in S_j$, then removing the edge from $c_i$ to $\ell$ and adding all connections from $\ell$ to the leaves of $S_i$ increases the bound. Then the LHS of our bounding claim results.