Assignment II: Nets and Graphs (Spring, 2015)

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://www.york.cuny.edu/~malk/

1. Consider the 1x1x1 metrical cube shown in Figure 1 (labeled for convenience):

Figure 1

Figure 2 shows the net obtained from the cube in Figure 1 when cuts are made along the edges of the tree (connected graph without circuits) in Figure 1 shown with thick dark edges.

Figure 2

Figure 3 shows the edges that were thick in Figure 1 which, when cut, lead to the "net" in Figure 2. Note the tree has 8 vertices, as does the cube.

Figure 3

Figure 4 shows Figure 3 with its vertices labeled to correspond to those that were cut to obtain Figure 2, labeled as the vertices of the cube were labeled in Figure 1..

Figure 4

The graph in Figure 4 (and Figure 3, where the labels are omitted) is a tree (connected graph with no circuits) and includes vertices that correspond to each vertex of the cube in Figure 1. Thus Figure 4 is a "labeled" spanning tree of the 3-cube. A spanning tree of a graph G is a tree where the vertices of the tree include all of the vertices of G.

Question 1:

Verify that there are at least 11 nets of the cube by drawing 10 additional diagrams similar to those in Figure 2 with, however, none of the diagrams being congruent to one another.

For each of the 10 additional nets N₁, ...,N₁₀ draw:

a. The net N_i (i going from 1 to 10)

b. A drawing of the cube labeled as in Figure 1 with thick darkened edges which show how to cut the edges of the cube to obtain net N_i.

c. A labeled plane drawing (using the labels as in Figure 1) of the spanning tree formed by the darkened edges you used in b. above to get N_i similar to what was done to obtain Figure 4 for the net in Figure 1.

Question 2.

For each of the integer sequences below, if possible, draw two non-isomorphic connected graphs without loops or multiple edges which have this sequence as its valence sequence or explain why there can be no graph or exactly one graph (up to isomorphism). If possible draw plane graphs.

a. 4, 4, 4, 4, 4, 4     i. 6, 4, 3, 3, 3, 2

b. 3, 3, 3, 3, 3, 3, 3, 3     j. 5, 3, 3, 1, 1

c. 2, 2, 2, 2, 2, 2, 2     k. 7, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2

d. 3, 3, 1, 1     l. 4, 4, 3, 3, 1, 1

e. 3, 3, 2, 1, 1

f, 3, 3, 2, 2, 1, 1

g. 4, 3, 1, 1, 1, 1, 1, 1

h. 5, 4, 4, 3, 3, 3, 2