Homework Three Quick Answers

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
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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

mersin escort adana escort izmir escort gaziantep escort