Graph Theory Lessons

Answers to Lesson 17


  1. Graph Components
    L12,1 1
    L12,2 2
    L12,3 3
    L12,4 4
    L12,5 1
    L12,6 6
    L12,7 1
    L12,8 4
    L12,9 3
    L12,10 2
    L12,11 1

  2. L25,15 has 5 components and L20,12 has 4 components.

  3. Ln,m has gcd(n,m) components First note that by symmetry all the components have the same number of vertices. Let us call this number k. We then have that the graph has n/k components.

    Consider the component that contains vertex 1. It has vertices 1, 1+m, 1+2m, ..., 1+(k - 1)m and then it repeats so 1 + km = 1 (mod n) Therefore k is the smallest number such that km is a multiple of n, i.e. km = lcm{m,n}. We now have

  4. Each component of Ln,m has n/gcd{n,m} vertices.

  5. Ln,m is isomorphic to the circuit Cn if gcd{n,m} = 1, i.e. n and m are relatively prime.

  6. Ln,r,s has gcd{n,r,s} components.

  7. Each component of Ln,r,s has n/gcd{n,r,s} vertices.
e-mail: C. Mawata
© C. Mawata