(a) Define a tree and what it means for a graph to be acyclic. Show that if $G$ is an acyclic graph on $n$ vertices then $e(G) \leqslant n-1$. [You may use the fact that a spanning tree on $n$ vertices has $n-1$ edges.]

(b) Show that any 3-regular graph on $n$ vertices contains a cycle of length $\leqslant$ $100 \log n$. Hence show that there exists $n_{0}$ such that every 3-regular graph on more than $n_{0}$ vertices must contain two cycles $C_{1}, C_{2}$ with disjoint vertex sets.

(c) An unfriendly partition of a graph $G=(V, E)$ is a partition $V=A \cup B$, where $A, B \neq \emptyset$, such that every vertex $v \in A$ has $|N(v) \cap B| \geqslant|N(v) \cap A|$ and every $v \in B$ has $|N(v) \cap A| \geqslant|N(v) \cap B|$. Show that every graph $G$ with $|G| \geqslant 2$ has an unfriendly partition.

(d) A friendly partition of a graph $G=(V, E)$ is a partition $V=S \cup T$, where $S, T \neq \emptyset$, such that every vertex $v \in S$ has $|N(v) \cap S| \geqslant|N(v) \cap T|$ and every $v \in T$ has $|N(v) \cap T| \geqslant|N(v) \cap S|$. Give an example of a 3-regular graph (on at least 1 vertex) that does not have a friendly partition. Using part (b), show that for large enough $n_{0}$ every 3-regular graph $G$ with $|G| \geqslant n_{0}$ has a friendly partition.