Exercises 58-64 refer to the complement of a graph. If G is a simple graph, the complement of G,…
Exercises 58-64 refer to the complement of a graph. If G is a simple graph, the complement of G, denoted G', is the simple graph with the same set of nodes as G, where nodes x-y are adjacent in G' if and only if they are not adjacent in G.
58. Draw G' for the graph of Figure 5.18a.
59. Draw K4. 60. Show that if two simple graphs G1 and G2 are isomorphic, so are their complements G. and G2.
61. A simple graph is self-complementary if it is isomorphic to its complement. Prove that in a self-complementary graph with n nodes (n > 1), n = 4k or n = 4k + 1 for some integer k. (Hint: Use the result of Exercise 19.)
*62. a. Prove that in any simple graph G with at least two nodes, if G is not connected, then G' is connected. (Hint: If G is not connected, then G consists of a collection of “disjoint” connected subgraphs.)
b. Find a graph G where both G and G' are connected, thus showing that the converse of part (a) is false.
63. Given an adjacency matrix A for a simple graph G, describe the adjacency matrix for G'.
64. Prove that if IN| 11 in a simple, connected graph G, then not both G and G' can be planar.
Find an expression for the number of arcs in Kn and prove that your expression is correct.