Cycles in Nets

A unit net in the plane is formed by taking a set of parallel horizontal lines at separations of one unit, and a set of parallel vertical lines also at separations of one unit. A square net is formed as follows: take any subset of the intersection points of a unit net; we will call the selected points vertices (singular vertex). Each two vertices at distance one unit are joined by a straight line segment; these segments are called edges. Since the diagonal distance between points is at least , the edges are necessarily all vertical and horizontal. Edges may not be omitted -- if two vertices have distance one, the edge joining them must be included.

Figures 1 through 4 illustrate square nets, and Figures 5 and 6 illustrate structures which are not square nets.

Notice that a square net with 4 vertices can have at most 4 edges, as illustrated in Figure 7, and one with 6 vertices can have at most 7 edges, as illustrated in Figure 8.

Question 1: What is the largest possible number of edges in a square net with n vertices if

(1a) n = 5?

(1b) n = 8?

(1c) n = 9?

(1d) Arbitrary integer n?

Explain your answers.

Question 2: A square net is bipartite if it is possible to label the vertices with the labels a and b so that no two vertices with the same label are joined by an edge, as illustrated in Figure 9. Every square net is bipartite. Explain why.

A cycle in a square net is a sequence of distinct vertices such that and are at distance one, and and are at distance one for each i with . In each of the square nets of Figures 10 through 12, the darkened edges are the edges of a cycle in that net. As seen in Figures 10 and 11, it is not necessary for every vertex of a square net to be in the cycle.

However, a cycle which does include every vertex is special; such cycles are called Hamiltonian after a famous nineteenth century mathematician. Figures 12 and 13 show Hamiltonian cycles in their square nets. We will explore the general question, ``Which square nets have Hamiltonian cycles?''

Question 3: A square net, such as the one in Figure 2, is called disconnected if there are two vertices in the net such that there is no way to get from one of the vertices to the other by travelling along edges of the net. A disconnected square net cannot have a Hamiltonian cycle. Explain why.

Question 4: A square net, such as the one in Figure 3, has a cut vertex if there is a vertex whose removal would disconnect the net. A square net with a cut vertex cannot have a Hamiltonian cycle. Explain why.

Question 5: A square net, such as that in Figure 4, which has an odd number of vertices cannot have a Hamiltonian cycle. Explain why. (Hint: Think about the labelling described in Question 2.)

A vertical strip is a square net like that shown in Figure 14, and a horizontal strip is a square net like that shown in Figure 15. The number of squares in a strip is the length of the strip. For example, the vertical strip of Figure 14 has length 4, and the horizontal strip of Figure 15 has length 5.

A rectangular square net is made up of a stack of horizontal strips, all the same length. The number of strips is the height of the rectangular square net, and the common length of the strips is the length of the rectangular square net. If a rectangular square net has height m and length n, we say it is an square net. The square net of Figure 12 is , of Figure 13 is , and of Figure 16 is . The rectangular square net of Figure 14 is , and the rectangular square net of Figure 15 is .

Question 6: Prove that an rectangular square net is Hamiltonian if either m or n (or both) is odd. Prove that it is not Hamiltonian if m and n are both even.

Note: To be complete, a proof must be general. It does not suffice to show certain examples can be done. However, doing examples helps in finding the general proof. Try some examples.

Call a square net a slope if it consists of a sequence of vertical strips of lengths in order from left to right. All rectangular square nets are slopes. Others are shown in Figures 17 through 19. We describe the slope by the sequence of numbers . Thus, the square net is a 4, 4, 4, 4, 4 slope, and the net shown in Figure 17 is a 7, 6, 6, 5, 5, 4, 4, 1, 1 slope. Figure 18 shows a 5, 4, 4, 2, 2 slope, and Figure 19 shows a 3, 3, 1, 1, 1 slope.

Question 7: Under what conditions does a slope have a Hamiltonian cycle? Deeply explore this question. For example, giving some infinite classes of slopes which do and some infinite classes which do not have Hamiltonian cycles will gain credit for your team.