$($i$)$ Prove that every simple graph $G=(V,E)$ contains a $3-$partite subgraph $G^{\text{'}}=$

$(V,E^{\text{'}})$ such that $|E^{\text{'}}|\frac{2}{3}|E|$

$($ii$)$ Design an algorithm that computes such a subgraph $G^{\text{'}}.$ Analyze the running

time of your algorithm. Try to make the running time of your algorithm as efficient

as possible in terms of the parameters $|V|$ and $|E|.$