Graph Theory Lessons
Answers to Lesson 19
-
Sqm,n has (m - 1)n + (n - 1)m = 2mn - n -m edges.
-
If m>1 and n>1,
-
Sqm,n has 4 vertices of degree 2.
-
Sqm,n has 2(m - 2) + 2(n - 2) = 2(m + n - 4) vertices of degree 3 .
-
Sqm,n has (m - 2)(n - 2) = mn - 2m - 2n + 4 vertices of degree 4.
-
The sum of the degrees of the vertices of
Sqm,n is
This agrees
with the answer to problem 1 as the number sum of the degrees is twice the number of edges.
If n > 1 and m > 1 then the chromatic number of Sqm,n is 2.
Sq1,1, Sq1,2, and Sq2,1 are regular of degree 1, while Sq2,2 is regular of degree 2.
(Use the program to find a Hamilton circuit in Sq4,3 and one in Sq4,4).
From problem 2, Sqm,n has
vertices. Therefore a Hamilton circuit in Sqm,n has mn edges. If a Hamilton circuit has r right moves, l left moves, u upward moves, and d downward moves then, since the circuit starts and ends at the same vertex, r = l and u = d. Therefore
If m and n are both odd, then this is impossible since the product mn is odd while 2r + 2u is even.
If Sqm,n has an Euler circuit then both m and n must be at least 2. Also, all the vertices must have even degree. From problem 2, there are 2(m + n - 4) vertices of degree 3 so we need m + n - 4 =0, i.e. . m = 4 - n as well as m > 1 and n > 1. We must therefore have m = n = 2.
A triangular grid always has an Euler circuit because is is connected and all of its vertices have even degree (2, 4, or 6).
e-mail: C.
Mawata
© C. Mawata