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.)
1. If possible draw connected graphs with the degrees, valences below. When possible try to avoid loops and multiple edges.
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.)
c. Determine all of the possible valences that the vertices of G can have if G has no-self loops or 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?
------------------------------------------------------------------------------------------------------------------
The valence of a vertex where there is no self-loop is the number of distinct edges at the vertex. A self-loop contributes two (2) to the valence of the vertex it is located at. In the graph above, the vertex were the self-loop appears has valence 3. The other vertices which are not 1-valent (there are three 1-valent vertices in this graph) have valences 5, 4, 3, 2, 2 and 2. Thus, a complete list of the valences for this graph are: 5, 4, 3, 3, 2, 2, 2, 1, 1, 1. The sum of the valences in a graph is twice the number of edges in the graph. Another name for the valence of a vertex is degree of a vertex. Computer scientists often refer to vertices with valence 1 as the leaves of a graph. The path shown has length 3 and the circuit also has length 3. A graph is called connected if between any two of its vertices one can move along edges between the vertices, that is there is a path between the vertices. Note that this graph has been drawn in the plane so that edges in the graph meet only at vertices. Drawings of this kind are known as plane drawings.