Exercises on graph theory

Just some exercises of Bondy's and Murty's book. I also added some from Trudeau's book and Bollobás book.

Exercise 1. Let $G$ be a simple graph. Then $||G||\leq \binom{|G|}{2}$ where $|G|:=|V(G)|$ and $||G||:=|E(G)|$. Determine when equality holds.
Proof. First, the cardinality of the set of unordered pairs of a set $V$ is bounded by $\binom{|V|}{2}$, from which the first result follows. Now, a graph $G$ is complete iff it has exactly $\binom{|G|}{2}$ edges. Indeed, $G$ is complete if and only if every unordered pair ${u,v}$ of elements of $V(G)$ is in $E(G)$, if and only if there are $\binom{|G|}{2}$ of them.

Exercise 2. Every path is bipartite and a cycle is bipartite if and only if its length is even.
Proof. Let $G$ be a path and $n=|G|$. Partition $V=V(G)=\{v_1,\dots,v_n\}$ in the two sets $V_1=\{v_i\in V\mid i\text{ is odd.}\}$ and $V_0=\{v_i\in V\mid i\text{ is even.}\}$. Since every path in $G$ has the form $\{v_i,v_{i+1}\}$, and $i\not\equiv i+1\mod 2$ for every $i$, then the partition is adecuate for $G$ to be bipartite.

Now suppose $G$ is a cycle with even length. Then $n$ is also even. The partition given before still works so $G$ is bipartite. Now suppose that $G$ has odd length. If $V_1,V_2$ were a 'bipartition' of $V(G)$, then, renaming $V_1$ and $V_2$ appropiately we can suppose that $v_1\in V_1$. Then, since $V_1,V_2$ make a bipartition of $G$, the vertices adjacent to $v_1$, say, $v_{2},v_{n}$, must be in $V_2$. By applying the same reasoning repeatedly (starting with $v_2$ instead of $v_1$, in an ascending way) we conclude that $v_j\in V_1$ for every $j\equiv 1\mod 2$ and $v_j\in V_2$ for every $j\equiv 0\mod 2$. But applying the same reasoning (starting with $v_n$ in a descending way) we conclude that $v_j\in V_2$ for every $j\equiv n\equiv 1\mod 2$ and $v_j\in V_1$ for every $j\equiv 0\mod 2$. It follows that $V_1=V_2=V(G)$, a contradiction.

Exercise 3. Show that for any graph $G$, $\delta(G)\leq d(G)\leq \Delta(G)$, where $\delta(G),d(G),\Delta(G)$ denote the minimum, average, and maximum value between the degrees of the vertices of $G$ respectively.
Proof. For any set $A\subseteq \mathbb{Z}$, $\min A\leq \mu A\leq \max A$, where $\mu(A)$ denotes the average of the elements of $A$. So just take $A$ as the set of the degrees of the vertices of $G$.

Exercise 4.  Let $G$ be a graph. Then $G$ or $\overline{G}$ is connected.

Proof. Let's suppose $G$ is not connected and partition $G$ in it's more than one connected components, i.e. the partition associated to the equivalence relation $v\sim v'$ iff $v=v'$ or there is a path $v\leadsto v'$. Take two vertices $v,v'$. If they are in different connected components, then there is a path $v\leadsto v'$ in $\overline{G}$. If they are in the same one, take other vertex $w$ in another connected component. Then there are two paths $v\leadsto w,w\leadsto v'$. The composite path is a path $v\leadsto v'$. So, anyway, there is a path $v\leadsto v'$, thus $\overline{G}$ is connected.

Exercise 5. The graph $C_5$ is the only self-complementary cyclic graph.

Proof. If $C_5=[v_1,v_2,v_3,v_4,v_5,v_1]$ then $\overline{C}_5=[v_1,v_3,v_5,v_2,v_4,v_1]\cong C_5$, so $C_5$ is self-complementary. Furthermore, since the degree of all the vertices of $C_n$ is two, then if $n\neq 5$ the degree of the vertices of $\overline{C}_n$ is $n-3\neq 2$, so $\overline{C}_n$ can't be cyclic if $n\neq 5$.

Exercise 6. If $G$ is self-complementary then $|G|\equiv 0,1\mod 4$.

Proof. If $G$ is self-complementary then $||G||=||\overline{G}||$, so
$$\frac{|G|(|G|-1)}{2}=||K_{|G|}||=2||G||.$$
Then $|G|(|G|-1)=4||G||$. Suppose $|G|$ is odd. Then $|G|-1$ is even, and $\frac{4||G||}{|G|-1}=|G|$ is odd. This means that $4\mid |G|-1$. Otherwise, suppose $|G|$ is even. Then, by the same reasoning, $|G|-1=\frac{4||G||}{|G|}$ is odd, so $4\mid |G|$. The result follows.