1.1) Please look at the program http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/lab4-2015-Dir/part1.cc

 http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/lab4-2015-Dir/out.xls to see the plot.

1.2)0,1,3,7,15,31,63,127,255,511,1023;; R(n) = 2 ^ n  -1 
Grows exponentially
Proof By Induction: Base case n=1 is trues

Induction Hypothesis: R(k) = 2 ^k -1 ,

To prove for k+1,

R(k+1) = 2 * R(k) + 1 = 2 * (2 ^ k  -1) +1 = 2 ^ (k+1)  -1 .

1.3 P(n) =P(n-1) + 2, P(4) = 4
P(n) = P(n-1) + 2   (1)
P(n-1) = P(n-2) + 2 (2)
...

P(5) = P(4) + 2     (n-4)
P(4) = 4            (n-3)

Adding all these equations, and cancelling the left and right parts, we get

P(n) = 2 *(n-4) + 4 = 2n-4

2.1 It has 5 nodes {Alice, Bob. Charles, Diana, Edwina}
It has 5 edges, Max degree is 3, average degree is (2+2+3+2+1)/5 = 2

2.2 A connected simple graph with 10 vertices almost all (but for one) distinct degrees are:
1,2,3,4,5,5,6,7,8,9

3.http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/Graph2015-4-3.cc

4. Max number of edges = n*(n-1)/2, average degree = n-1 , max degree = n-1