```
Computer Science 575 / Mathematics 513
Combinatorics and Graph Theory

1. A graph is regular if all of its vertices are of the same degree. Suppose G is regular, and has 40 edges.
What is the fewest number of vertices this graph can have? Be sure to justify your result.
Draw the complement of this graph. What is the greatest number of possible vertices?
Again, justify your result.  Draw this graph. Are either of these graphs planar? Justify these conclusions also.

2E =  d*V, where d is the common degree of all of the vertices. Thus V must divide 80 evenly(and of course d < V).
So V = 10, d = 8. (V = 8 loses, since then the degree of all of the verts = 10).
Then the complement of the graph is a graph with 5 unconnected edges. Graph could have 40 edges, 80 verts of degree 1.
Thats planar, but first one isnt, since 80 > 3V - 6

2. The degree sequence of a graph presents the degrees of each vertex in the graph. Consider the following degree sequence:
(5 4 4 4 3 1),
which says that the graph in question has a total of 6 vertices, including one vertex of degree 5,
three vertices of degree 4, and so forth. Draw a graph with this degree sequence, or prove that one cannot exist.

No chance: 3 verts of odd degree.

3. Prove that in any graph G, either G or its complement, G-complement, is connected.
(Hint: assume that G is not connected, since if G is connected, then we are done).

Suppose G isnt connected. Then verts in different components  in G are directly connected in the complement,
and verts in the same component in G are connected by a length 2 path in G-complement, since
both are connected to same vert(s)  (all verts) in some other component.

4. Suppose every edge in K6 is arbitrarily colored either red or blue. Prove that there must be a monochromatic triangle.
That is, prove that for any edge coloring using these two colors there must exist a triangle that is either all red or all blue.
(Hint: show first that for any vertex in this graph, at least at least three of its incident edges must be of the same color.)

Done in class..

5. Give a minimal a-z cut for the flow network  displayed below.

Just do FF algorithm on any old network, e.g. the first problem in assignment 6

.

```

-- RobbieMoll - 09 Mar 2004

Topic revision: r1 - 2004-03-09 - 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