46  Homework I: Graph Theory

46.1 Vertex and edge sets

Figure 46.1: A simple graph.

Consider the graph shown in Figure 47.1:

1. Write down the vertex set of the graph:
   
   A, B, C, D, E, F, G, H, I, J, K
   
   
   VA, VB, VC, VD, VE, VF, VG, VH, VI, VJ, VK

2. Write down the edge set of the graph:
   

AC,

BC,

AE,

CF,

DF,

AG,

BG,

EG,

AH,

CH,

FH,

GH,

BI,

CI,

BJ,

HJ,

BK,

GK,

HK,

46.2 Node Neighborhoods

1. Write down the neighborhood of node C
   A, B, F, H, I
   

2. Write down the neighborhood of node K
   B, G, H
   

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

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

5. What is the union of the neighborhoods of nodes F and A?
   C, D, H, E, G
   

46.3 Graph Metrics

1. What is the order of the graph?
   11
   

2. What is the size of the graph?
   19
   

3. Write down the graph’s degree sequence:

H	B	C	G	A	F	K	E	I	J	D
6	5	5	5	4	3	3	2	2	2	1

1. Write down the graph’s maximum Degree:
   6
   

2. Write down the graph’s minimum degree:
   1
   

3. What is the graph’s degree range?
   5
   

4. What is the graph’s sum of degrees?
   38
   

5. What is the graph’s average degree?
   3.455
   

6. What is the graph’s maximum size?
   55
   

7. Compute the density of the graph:
   0.345
   

46.4 Subgraphs

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

Figure 46.2: A node deleted graph.

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

D