Section 7.2 #24

Cardinality	Number of sets of vertices	Maximum possible number of edges	Number of sets of edges
1	C(4,1)=4	0	1
2	C(4,2)=6	1	2
3	C(4,3)=4	3	2^3=8
4	C(4,4)=1	6	2^6=64

Answer=4*1+6*2+4*8+64*1=112

Section 7.2 #36

Let v and v-k be the number of edges in two parts of the graph. Number of edges f(k)=k*(v-k) will be maximum when k=v/2. Therefore the maximum number of edges is (v^2)/4

Section 7.3 #24

All of you seemed to know how to answer this question.

Section 7.3 #54

1. There are two possible graphs, one with 0 edges and another with 1 edge
2. There are four graphs one each corresponding to 0, 1, 2 and 3 edges
3. 0 edges: One possibility

1 edge: one possibility

2 edges: two possibilities (edges connected or not connected)

3 edges: three possibilities

• three edges meet at a vertex
• a path without circuit (different from the one above)
• a circuit

4 edges same as 2

5 edges same as 1

6 edges same as 0

Section 7.4 #14

Let v be a vertex with odd degree in G. Let H be the connected component of G. H is a graph and theorem 2 in section 7.2 implies that there must be atleast another vertex w with odd degree. Since H is connected, there is a path from v to w.