Assignment 1

1. Prove that if \(G\) is a graph of order at least 5, then \(G\) and its complement \(\bar G\) cannot both be bypartite.
2. Prove that if two graphs \(G\) and \(H\) are connected, then their cartesian product \(G\times H\) is also connected. Also establish a relation between the diameters of the three graphs.
3. Can we have a graph of order \(6\) with \(\delta(G) = 1\), \(\Delta(G) = 5\), and at least three vertices of degree \(4\)? Either explicitly construct such a graph, or prove that it is not possible.