**Geometric Structures: Problem Set C (Basic Graph Theory)**

Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

__malkevitch@york.cuny.edu__

web page:

__http://york.cuny.edu/~malk/____
__(See diagram below for help with the some basic graph theory terms.)

a. Determine all of the possible valences that the vertices of G can have if G has no-self loops? (Draw diagrams of some typical graphs that achieve the valences you find.)

b. Determine all of the possible valences that the vertices of G can have if G has no multiple edges? (Draw diagrams of some typical graphs that achieve the valences you find.)

d. Determine all of the possible valences that the vertices of G can have if G is connected and has no-self loops? (Draw diagrams of some typical graphs that achieve the valences you find.)

e. Determine all of the possible valences that the vertices of G can have if G is connected and has no multiple edges? (Draw diagrams of some typical graphs that achieve the valences you find.)

f. Determine all of the possible valences that the vertices of G can have if G is connected and has no-self loops or multiple edges? (Draw diagrams of some typical graphs that achieve the valences you find.)

2. Can you develop a general result (based on what you learned by doing Exercise 1) that deals with a graph H whose vertices all have the same valence and has k edges where k is a positive integer?

------------------------------------------------------------------------------------------------------------------