91Ó°ÊÓ

Draw a graph having the given properties or explain why no such graph exists. Simple graph; six vertices having degrees 1,2,3,4,5,5

Show that if a simple graph \(G\) has 11 or more vertices, then either \(G\) or its complement \(\bar{G}\) is not planar.

Find a formula for the number of edges in \(K_{n}\).

An \(r\) -regular graph is a graph in which all vertices have degree \(r\). A regular graph is a graph which is regular for some \(r\). Show that for each \(r\), all connected, simple, 3 -vertex, \(r\) -regular graphs are isomorphic.

Draw a graph having the given properties or explain why no such graph exists. Simple graph; five vertices having degrees 2,3,3,4,4

An \(r\) -regular graph is a graph in which all vertices have degree \(r\). A regular graph is a graph which is regular for some \(r\). Show that for each \(r,\) all connected, simple, 4 -vertex, \(r\) -regular graphs are isomorphic.

Let \(G\) be a bipartite graph with disjoint vertex sets \(V_{1}\) and \(V_{2}\), as in Definition \(8.1 .11 .\) Show that if \(G\) has a Hamiltonian cycle, \(V_{1}\) and \(V_{2}\) have the same number of elements.

Let \(A\) be an adjacency matrix of a graph. Why is \(A^{n}\) symmetric about the main diagonal for every positive integer \(n ?\)

Find a formula for the number of edges in \(K_{m, n}\).

What must a graph look like if some row of its incidence matrix consists only of 0 's?