Exercises for Chapter 1 of Hage and Harary book

• 1. In Figure 1.1, page 4, suppose the nodes represent people, and the edges represent friendship.
  • (a) With four nodes, how many possible edges are there? Which, if any, of the possible edges are absent from this graph?
  • (b) Redraw the diagram, placing nodes in the positions:

                    1      3
    
                    
                    4      2 
    

    Now draw in the edges, producing a visually distinct diagram representing the same graph.
  • (c) Label the graph with names beside the numbers, with 1=Alice, 2=Carlos, 3=Bill, 4=Dolores. Using the original diagram, in the book, which two people are not friends?
  • (d) Using the diagram you redrew in part (b), which two people are not friends?
  • (e) Construct an adjacency matrix equivalent to the one in the book, but with rows and columns ordered alphabetically, by the people's names, rather than numerically.
  • (f) Construct a list of edges, using names rather than numbers. For example, the edge 1,2 would be described instead as Alice,Carlos.
• 2. In Figure 1.9, page 13, construct a new graph by deleting nodes a, b, c, d, and the five edges that touch those nodes. The new graph should contain 7 nodes, e through k; and 8 edges connecting pairs of those nodes. One representation of the new graph could be obtained by simply covering up the left side of the diagram in the book.
  • (a) Is this new graph a "tree"?
  • (b) If not, list as many as you can of the "cycles" that keep it from satisfying the definition of "tree".
  • (c) If it is not a tree, omit this part. If it is a tree, is it also a "rooted tree"?
  • (d) A "spanning set" is a set of edges that make it possible to get from any node of the graph to any other node of the graph by going along a sequence of edges in that set. (The book discusses a special type of spanning set that is also a tree.) See how many of the 8 edges you could remove, while the remaining edges would still form a "spanning set"?