The Petersen program allows you to easily draw rectangular grids. Click Graph | Named Graph | Grid. When asked for the number of vertices high enter 4 and when asked the number of vertices across enter 3. You will get a graph like figure 42.1. If m>1 and n>1 we shall call an m by n rectangular grid Gridm, n.
Use the program to examine some grid graphs and answer the following questions:
- Look at the statistics of a few rectangular grids and find a formula for the number of edges in Gridm, n. Hint: How many horizontal edges and how many vertical edges are there?
If m>1 and n>1,
- How many vertices of degree 2 does Gridm, n have?
- How many vertices of degree 3 does Gridm, n have?
- How many vertices of degree 4 does Gridm, n have?
- What is the sum of the degrees of the vertices of Gridm, n? Does that agree with your answer to question 1?
- What is the chromatic number of Gridm, n?
- If Gridm, n is regular then what are the possible values of m and n?
- Find a Hamilton circuit in Grid4, 3 and one in Grid4, 4 .
If m and n are both odd
then Gridm, n
has no Hamilton circuit. You might try to check
Grid3, 3 or
but be warned that
for large values if your machine is not fast
it takes a very long time
for the program to
exhaust all the possibilities and give up trying.
To prove that
there is no Hamilton circuit answer the following
- How many vertices are there in Gridm, n?
- How many edges will there be in a Hamilton circuit on Gridm, n?
- Suppose that in a Hamilton circuit you have r right moves, l left moves, u upward moves and d downward moves. How are r and l related and how are u and d related?
- If h is the total number of edges in the Hamilton circuit then h=r+l+u+d. Why is this impossible?
- Clearly Grid2, 2 has an Euler circuit . Is there any other square grid with an Euler circuit? (Grid1, 1 doesn't count!) Hint: Use your answer to question 2.
© C. Mawata