Homework Three Quick Answers

- 1. Choose a max length path in G with endpoints a, b. Take a. Its links must go back into path, else path could be extended. Since it has d links, the link closest to b must be at least d away from a, creating a circuit of length d+1 or greater.
- 2. 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. Counterexample: K4.
- 4. Pictures.
- 5. Some vertex must have degree > N/2, which means that a bipartite split would divide the vertices into sets of size (N/2 + k), (N/2 -k), for k>0. This yields N**2/4 - k**2 edges, for k**2 > 0.
- 6. Pictures. Planar, start with two congruent triangles facing the same way, then add arcs to reach desired sequence. For nonplanar, start with K3,3, add two more edges.
- 7. 2N edges by handshaking lemma, so 10 = 2N - N +2, N = 8.
- 8. One of K, K-bar must have 28 edges, since K11 has 55 edges. This violates E<= 3V-6. If not connected then if planar, just add a connecting link between component(s).
- 9. Having a fourth circle, assuming general position, will violate R = E-V + 2.

`\-- Main.RobbieMoll - 2012-02-28`

This topic: Moll575 > Hwk3Ans

Topic revision: r2 - 2014-10-08 - 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

Ideas, requests, problems regarding UMass CS EdLab? Send feedback