```1. 1-supp-4 (p. 49)
11 vertices is minimum. K11 has 55 edges, K10 has 45

2. 1-supp-10
Consider (a) shortest path from a to b, where a, b not
directly connected. If pathlength = 2: done. If longer,
there cant be any shortcuts, so no chord can be present

3. 1.3 - 4
|V| must be odd. So total possible connections at any
vertex is even. Thus if x has odd deg in G, has odd in
complement, even in G, then even in complement. So all
but one have odd degree in G-bar.

4. 1.3 - 12
Left is: a,c,b,d one partition. Right one has odd cycles

5. pictures..

6. 1.4 - 8
2E = 4V. plugging in, V = 8

7. 1.4 - 16
either G or G-bar has at least 28 edges. Contradicts
Euler E <= 3V-6
8. 1.4  24
(a)use: 2E = d2R; 2E = d1V. (b) plug in to Euler & simp.
(c)multiply (d1-2)(d2 - 2).(d)(3 3)(3 4)(4 3)(3 5)(5 3)

9. 1.4  26
The 3 circle problem satisfies Euler. IF the 4th circle
cuts all regions, assuming general position, then Eulers formula no longer holds

10. 1.4  27  pictures..

```
-- RobbieMoll - 29 Sep 2006
Topic revision: r1 - 2006-09-29 - RobbieMoll    Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback