Proof about existence subgraph in graph I need help with my math problem.
Let $G$ be a graph with $n$ nodes and more than $\dfrac{3 (n - 1)}{2} $ links. Show that $G$ contains some $\theta a,b,c$ graph as its subgraph.
$\theta a, b, c$  is graph with three paths.
 A: Let $G$ be a counterexample with the smallest number of nodes, and with $e$ edges.  Hence $G$ is connected.  The average degree in $G$ is $$\frac{2e}{n}>\frac{3(n-1)}{n}=3-\frac{1}{n}.$$  Hence there is a vertex $v$ of degree $3$ or more in $G$.


*

*Case I: $v$ has three neighbors, $r$, $s$ and $t$, which belong to the same connected component in $G \setminus v$.  By assumption, there is a path from $r$ to $s$ not including $v$.

There must also be a path from $t$ to $s$ not including $v$ (or $t$ might even belong to $P$).  Thus, there is a shortest path from $t$ to a vertex in $P$.

Together, these identify a theta subgraph.

*Case II: $G \setminus v$ consists of the connected components $C_1,C_2,\ldots,C_k,D_1,D_2,\ldots,D_s$, where any $C_i$ contains exactly one neighbor of $v$ and any $D_i$ contains exactly two neighbors of $v$.
Suppose $C_i$ has $a_i$ edges and $b_i$ vertices, and suppose $D_i$ has $\overline{a}_i$ edges and $\overline{b}_i$ vertices.  Then the number of edges in $G$ is $$e=\sum_{i=1}^k a_i+\sum_{i=1}^s \overline{a}_i+k+2s$$ and the number of vertices is $$n=\sum_{i=1}^k b_i+\sum_{i=1}^s \overline{b}_i+1.$$
If $a_i+1 > \frac{3}{2}b_i$ for any $i \in \{1,2,\ldots,k\}$, then the subgraph induced by $C_i \cup \{v\}$ is a smaller counterexample.  Hence $a_i \leq \frac{3}{2}b_i-1$ for all $i \in \{1,2,\ldots,k\}$.
If $\overline{a}_i+2 > \frac{3}{2}\overline{b}_i$ for any $i \in \{1,2,\ldots,s\}$, then the subgraph induced by $D_i \cup \{v\}$ is a smaller counterexample.  Hence $\overline{a}_i \leq \frac{3}{2}\overline{b}_i-2$ for all $i \in \{1,2,\ldots,s\}$.
Hence
\begin{align*}
 e & = \sum_{i=1}^k a_i+\sum_{i=1}^s \overline{a}_i+k+2s \\
   & \leq \sum_{i=1}^k \left(\frac{3}{2}b_i-1\right)+\sum_{i=1}^s \left(\frac{3}{2}\overline{b}_i-2\right)+k+2s & \text{as explained above} \\
   & = \sum_{i=1}^k \frac{3}{2}b_i+\sum_{i=1}^s \frac{3}{2}\overline{b}_i-(k+2s)+k+2s \\
   & \leq \frac{3}{2}(n-1).
 \end{align*}
This contradicts that $G$ is, in fact, a counterexample.
