45  Homework I: Graph Theory

45.1 Vertex and edge sets

Figure 45.1: A simple graph.

Consider the graph shown in Figure 45.1:

  1. Write down the vertex set of the graph:



  2. Write down the edge set of the graph:



45.2 Node Neighborhoods

  1. Write down the neighborhood of node C



  2. Write down the neighborhood of node K



  3. What is the intersection of the neighborhoods of nodes C and K?



  4. What is the intersection of the neighborhoods of nodes G and H?



  5. What is the union of the neighborhoods of nodes F and A?



45.3 Graph Metrics

  1. What is the order of the graph?



  2. What is the size of the graph?



  3. Write down the graph’s degree sequence:



  4. Write down the graph’s maximum Degree:



  5. Write down the graph’s minimum degree:



  6. What is the graph’s degree range?



  7. What is the graph’s sum of degrees?



  8. What is the graph’s average degree?



  9. What is the graph’s maximum size?



  10. Compute the density of the graph:



45.4 Subgraphs

  1. Go back to Figure 45.1. Draw the node-deleted subgraph of this graph that excludes nodes F, and H.



























  2. List the isolate nodes in the node-deleted subgraph you obtained in the previous step.