Computer Science 575 Math 513 - Fall 2014

Homework 3

You may collaborate on #2,8,9

1. Suppose d > 1, and for graph G every vertex has degree >= d. Show that G must therefore have a circuit of length at least d + 1.

2. If G is a connected undirected graph that is not complete, show that some vertex, call it x, has two neighbors, say y and z, that are not adjacent to each other. Thus, (x,y) and (x,z) are edges in G, but (y,z) is not.

3. Prove, or give a counterexample to the following assertion: "A graph with n vertices and n+2 edges must contain 2 edge-disjoint circuits."

4. Consider a collection of circles (of varying sizes) in the plane. Make a circle graph with a vertex for each circle and an edge between two vertices when they correspond to two circles that cross. (There is no edge when one circle properly contains another.)

  • Draw a family of circles whose circle graph is isomorphic to K4
  • Draw a family of circles whose circle graph is isomorphic to K3,3
5. Show that a graph with N vertices and more than (N**2)/4 edges cannot be bipartite. (Note (N**2) is "N-squared")

6. Given this degree sequence: (4,4,4,4,3,3), find two graphs with this degree sequence, one planar, and the other nonplanar.

7. If G is a connected planar graph with N vertices, all of degree 4, and with 10 regions, what is the value of N?

8. If G has 11 vertices, prove that one of G and G-bar (the complement of G) must be nonplanar.

9. Consider an overlapping set of 4 circles A,B,C,D. One would like to postition the circles so that every possible subset of the circles forms a region, e.g., 4 regions containing just one circle, 6 regions containing some of two circles (AB, AC, AD, BC, BD, CD), 4 regions formed by the intersections of 3 of the 4 circles, and 1 region formed by the intersection of all 4 circles. Prove that it is not possible to have such a set of 15 bounded regions.

Due: September 23, in class

-- Main.RobbieMoll

Topic revision: r9 - 2014-09-12 - 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