image
Graph Theory Lessons

rule

previous index next Lesson 42: Grids

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.

Grid(4, 5)
Fig 42.1, The graph Grid4, 5

Questions:
Use the program to examine some grid graphs and answer the following questions:
  1. 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?
  2. 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?
  3. What is the chromatic number of Gridm, n?
  4. If Gridm, n is regular then what are the possible values of m and n?
  5. Find a Hamilton circuit in Grid4, 3 and one in Grid4, 4 .
  6. If m and n are both odd then Gridm, n has no Hamilton circuit. You might try to check Grid3, 3 or Grid5, 5 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 questions:
    • 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?
  7. 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.

Answers


© C. Mawata