**Geometric Structures: Sheet B (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. 1, 1, 1, 1

b, 1, 1, 1, 1, 1, 1

c, 2, 2, 2

d, 2, 2, 2, 2

e. 3, 3, 3, 3

f, 3, 3, 3, 3, 3, 3

g, 3, 3, 3, 3, 3

h. 4, 4, 4, 4, 4

i. 4, 4, 4, 4, 4, 4

(Can you formulate any general "theorems" based on what you discovered by doing the examples above?)

j. 6, 5, 4, 3, 3, 3, 2, 2, 2

k. 6, 5, 4, 3, 3, 2, 2, 2

l. 6, 5, 4, 3, 3, 3, 3, 3, 2, 2, 2

m. 6, 5, 4, 3, 3, 2, 2

n. 2, 2, 2, 2, 1, 1, 1, 1

o. 3, 2, 2, 2, 1, 1, 1

2. A graph G has 8 edges and all of its vertices have the same valence.

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?

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