Week 5

Operations:

S = {x | x 4 = 1} ⊗ is defined as multiplication.  (i.e., S={1,-1,i,-i}) , 1 is identity and (-1)² = 1

and

S = {0,1,2,3} ⊗ is defined as addition modulo 4. 0 is identity and (2)² = 0

In both systems:

i) |S| = 4

ii) ∀x, y ∈ S , x⊗y ∈ S

iii)  ∃i ∀x∈S i⊗x = x

iv) ∀x∃y  y⊗x = i

v) ∀x, y ∈ S , x⊗y = y⊗x

vi) the other big one (?you should know?)

Show that both systems are isomorphic.

Homework H1: Find another operation defined on four elements that satisfies all of the above equations but which is not isomorphic to these. Show that the operation satisfies all six properties above. Prove that your group is not isomorphic to the group defined above (e.g., addition modulo 4)..

Graphs and trees (continuing from Chapter 1 in Hein)

Definitions of path, walk, distance. Eulerian trail and Eulerian cycle. Hamiltonian path. Cycle and tree.

Demonstrations:

showing two trees are the same

showing two graphs are not the same

Exercise: construct a graph which has each node with different degree.

Homework:

Reading: Chapter 2 in Hein

Assignment #5 - due Feb. 11 (Wednesday)

For those of you lacking in HTML knowledge, this link may help.

 Assignment #6 - due Wednesday  Feb. 18:

Exercise H1: above (hint, suppose x²=identity for all x in S)

Show that these two graphs are isomorphic:

Prove or disprove the claim that any two three-regular graphs on six nodes are isomorphic.

Construct two different 3 regular graphs each having 8 nodes. Demonstrate that they are not the same.

Page 71, exercises 13 and 14.