Probabilistic method and graph theory 
*

*Let $G$ be a simple graph with maximum degree $9$ and $e$ edges. Show that we can partition the set of vertices into two sets such that the number of edges between two set is at least $\frac{5}{9}e$.

*Show that there is a graph on $n$ vertices with at least $O(n^{4/3})$ edges and without any square.
 A: Here's a solution to problem 2:
We construct a random graph on $n$ vertices by adding each edge with probability $p$, independently and uniformly.  Thus, the expected number of edges is $p\binom{n}{2}$.  For every collection $S$ of four vertices, we have that the probability they form a square is $p^4$.  For every square that is formed, we remove one edge, thereby removing the square from the graph.  Thus, the expected number of edges is greater than or equal to $$ p \binom{n}{2} - 3 p^4 \binom{n}{4}.$$  Taking $p = n^{-2/3}$ gives that this expectation is $O(n^{4/3})$, implying there is a graph with no squares having at least $O(n^{4/3})$ edges.
A: For Problem 1: Let $\sigma$ be an ordering of the vertices of $G$ (i.e. a permutation of the $n$ vertices of $G$).  Call a vertex $v$ good if there are an odd number of neighbors of $v$ appearing before $v$ in $\sigma$.  
Claim 1: Let $v$ be a vertex of degree $d(v)$.  If $d(v)$ is odd, then $v$ is good for exactly half of all possible orderings.  If $d(v)$ is even, then $v$ is good for a $\frac{d(v)}{2d(v)+2}$ fraction of all possible orderings.    
Proof: The goodness of $v$ depends only on the relative ordering of $v$ and its $d(v)$ neighbors, so it suffices to consider permutations only of those $d(v)+1$ vertices.    Let $\tau \in S_{d(v)}$ be the relative permutation of the neighbors.  For each $\tau$, there are $d(v)+1$ places we can insert $v$ in this ordering to create a permutation of $d(v)+1$ vertices, all of which are equally likely.  The vertex $v$ is good if we insert $v$ after $1, 3, 5, \dots$ vertices.  This means there's $(d(v)+1)/2$ good places to insert $v$ if $d(v)$ is odd, and $d(v)/2$ good places if $d(v)$ is even.  
Claim 2: There is a choice of $\sigma$ such that there are at least $$\frac{n}{2} - \sum_{v \textrm{ with }\atop d(v) \textrm{ even}} \frac{1}{2d(v)+2}$$ good vertices.  
Proof: Consider a randomly chosen $\sigma$.  The expected number of good vertices is equal to the sum over all $v$ of the probability that $v$ is good.   We found this probability in Claim $1$, and the formula here corresponds to adding all that up.  
Claim 3: There is a partition of the vertices with at least 
$$\frac{e}{2} + \frac{1}{2} \left(\frac{n}{2} - \sum_{v \textrm{ with }\atop d(v) \textrm{ even}} \frac{1}{2d(v)+2}\right)$$
edges crossing between the two halves.  
Proof: Fix a $\sigma=(v_1, v_2, \dots, v_n)$ satisfying the conclusion of Claim $2$.  We now partition the vertices of $\sigma$ in order, putting each $v_j$ on whichever side creates more crossing edges between $v_j$ and $\{v_1, \dots, v_{j-1}\}$.  Let $a_j$ be the number of edges between $v_j$ and earlier vertices.  There will always be a choice of sides which creates at least $\lceil \frac{a_j}{2} \rceil$
crossing edges.  This is equal to at least $\frac{a_j}{2}$, but we get an extra half edge every time $v$ is good.  These additional half edges correspond to the second term in the claim.  
Claim 4: For any $G$ with maximum degree $9$, there is a partition with at least $\frac{5e}{9}$ edges.
Proof: Think of the expression in claim $3$ as 
$$\frac{e}{2} + \frac{1}{4} \sum_v f(v),$$
where 
$$f(v) = \left\{ \begin{array}{cc} 1 & \textrm{ if } d(v) \textrm{ is odd } \\ 1- \frac{1}{d(v)+1} & \textrm{ if } d(v) \textrm{ is even } \end{array}\right.$$
It can be checked by direct calculation that $f(v) \geq \frac{1}{9} d(v)$ whenever $d(v) \leq 9$ (equality holding both for $d(v)=8, f(v)=\frac{8}{9}$ and $d=9, f(v)=1$).  So the number of crossing edges is at least 
$$\frac{e}{2} + \frac{1}{4} \sum_v \frac{1}{9} d(v) = \frac{e}{2} + \frac{1}{18} \left(\frac{1}{2} \sum_v d(v) \right) = \frac{e}{2} + \frac{1}{18} e = \frac{5e}{9}.$$
A: For path I. 
Consider complete graph that has $|E(G)|=\frac{n(n-1)}{2}$ number of edges, an example about simple graphs. Show first that $K_n$ satisfy the condition and prove inductively on each spanning subgraph of $K_n$ such as $K_k -h$ where $h$ is an edge satisfy the condition. Your goal is to show that the condition is satisfied with every simple subgraph.
I haven't proved this but the below shows the idea. You may need to partition again after the removal to satisfy the condition again.
Example
Consider $K_{9}$ with vertex sets $S$ and $H$: you start with all vertices in $S$. Move one vertex to $H$ so nice edges between $S$ and $H$. Move second vertex to $H$ so $(9-1)+8=16$ vertex between $S$ and $H$. You can increase the number of edges between $S$ and $H$ until 4 vertices in $S$ and $5$ in $H$. So $9+8+7+6 \geq 4*5=20$ vertices between $S$ and $H$ is the maximum edge count. $4+3+2+1=10$ edges in $H$ and $3+2+1=6$ edges in $S$. And $|E(K_9)|=36 =20+10+6$. Notice that $5/9\cdot |E(G)|=5/9\cdot 36=20$ so the condition is satisfied. 
Now remove an edge $h$ between the sets $S$ and $H$ so the graph $G-h$ has 35 edges so $5/9\cdot 35=19.4444....> 19$ so the condition is not satisfied. This means the graph $K_9-h$ must be partioned again until again 20 edges between $S$ and $H$. In next removal, $34\cdot 5/9>19$ so only 19 edges now required between $S$ and $H$.
