# graph thepry help

• Nov 18th 2008, 02:58 PM
jeremy.ambler
graph thepry help

1.
(a) how many labeled graphs are there on n vertices?
(b) how many of these have exactly m edges?

2. Are any of the following degree sequences graphic? If so, draw the graphs...if not, explain why. If you determine the sequence is graphic, work backwards to draw the graph.
(a) 6, 6, 5, 5, 2, 2, 2, 2
(b) 6, 6, 5, 5, 3, 3, 3, 3)

3. Can 9 line segments be drawn in the plane, each of which intersects exactly 3 others? Difficulty here is HOW to draw a graph associated with the problem.

4. Prove (n, n, n-1, n-1, ..., 4, 4, 3, 3, 2, 2, 1, 1) is graphic for every n>=1 . Use induction.

5. Prove that for any positive integer n>=5, there exists a graph with n vertices, all of which have degree 4. Use induction.

6. Suppose G is a graph with no cycles of length 3, where every vertex has degree k.
(a) Show that G has at least 2k vertices. All is needed is a picture.
(b) If G has exactly 2k vertices, what does it look like? Make sure your answer works for every value of k = 1,2,3...

7. A bridge is an edge in a connected graph whose removal disconnects the graph.
(a) Show that a connected graph with all degrees even cannot have a bridge. Hint: Suppose it did have a bridge. What happens when you remove it?
(b) On the other hand, for every odd number n, construct a connected graph G where every vertex has degree n and G has a bridge.
Draw it for n = 1 (easy) and n = 3 (harder). Study the n = 3 case and make something similar work for larger odd n.

8. There are 50 scientists at a conference and each of them is acquainted with at least 25 of other others. Show that there are four of them who can be seated at a round table so that each of them has two acquaintances for neighbors.
This can easily be solved using a picture.