# Automorphism proof (graph theory)

1. Mar 5, 2016

### TheMathNoob

1. The problem statement, all variables and given/known data
The problem is attached and it's part A. There is no need to put problem 4 hence the problem is fully explained in the file attached

2. Relevant equations
Zk is mod k basically.

3. The attempt at a solution
I know that we have to prove that the transformation is onto,one to one and preserves adjacency.
It's one to one because
T(s1)=T(s2)
s1+v=s2+v
s1=s2

It's onto because
y=s+v
y-v=s
T(s)=T(y-v)=y-v+v=y
I am not quite sure how to show that it preserves adjacency because I can't apply the concept of hamming distance anymore.

#### Attached Files:

• ###### Screenshot (14).png
File size:
76.1 KB
Views:
40
Last edited: Mar 5, 2016
2. Mar 5, 2016

### andrewkirk

Two vertices are adjacent iff they have identical coordinates in all dimensions except for one.

Say $U$ and $V$ are adjacent because their coordinates are identical except for the $j$th one.

For which, if any, of $u\in\{1,2,...,n\}$ are the $u$th coordinates of $T(U)$ and $T(V)$ equal?

3. Mar 6, 2016

### TheMathNoob

Yes except for the jth coordinate?

4. Mar 6, 2016

### andrewkirk

Yes, and what does that tell us about whether T(U) and T(V) are adjacent?

5. Mar 6, 2016

### TheMathNoob

T(U) and T(V) are still adjacent because all their coordinates are the same except for the jth one.

6. Mar 6, 2016

### TheMathNoob

I had another problem. I would be glad if you take a look.