# 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

 Home Moll575 Web View Edit Account
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