Figure 1 (Graph H)
Assignment I (Spring, 2015)
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
1. Assume the vertices of the graph H shown in Figure 1 have been numbered starting with the number 1 for the vertex at the top, and then consecutively from left to right and from top to bottom.
a. How many vertices does H have?
b. How many edges does H have?
c. Write down the valences of all of the vertices of H.
d. Draw a graph with the same valences as H which is not isomorphic to H.
e. If the drawing of H is not a plane drawing, but H is a planar graph, draw a graph H* isomorphic to H where the drawing of H* is a plane drawing. If you succeed in drawing a plane graph write down the number sides of the faces that the regions of your plane graph has.
f. If H has an Eulerian circuit write one down that starts at vertex 3. If H has no Eulerian circuit explain why.
g. If H has a Hamiltonian circuit write one down starting at vertex 5. If H has no Hamiltonian circuit give an argument why it has none.
2. A tree is a connected graph without circuits.
a. Can you draw a tree T with valences 5, 1, 1, 4, 1, 1, 3, 1, 1, 1, 1?
b. If the answer to a. is yes, can you draw another tree with the same valences that is not isomorphic to T?
c. Can you give a sequence of valences for which a tree can be drawn but there is no other non-isomorphic tree with the same valences?
3. Can you construct a valence sequence for which one can construct a graph G with this valence sequence, but there is no other graph with this valence sequence which is not isomorphic to G?