Question

Let G be a graph with
V(G)={1,...,2n}
E(G)={{2i-1,2i}: 1<=i<=n}

In general how many automorphisms (including the identity automorphism) are there for G?

Answer 1

You're going to have to use the definition of automorphism here.

Answer 2

I'm a little unsure of exactly what an automorphism implies. Does it need to retain the same shape as the original graph?

Answer 3

Going to need a proper definition.

Answer 4

for two graphs to be isomorphic there must be a bijection f:V(G1)->V(G2) such that verticies f(u)and f(v) are adjacent in G2 iff u and v are adjacent in G1. An Isomorphism from G to itself is called an automorphism.

Answer 5

this page shows an example of isomorphism http://mathworld.wolfram.com/GraphAutomorphism.html

Answer 6

Well, if we considered n=2, then the vertices are
{1,2,3,4}
The edges would be
{(1,2), (2,4)}

Answer 7

I got 16 automorphisms when I tried n=2. But I'm not sure if all of them are correct

Answer 8

If you changed 2 to be any other number, then you must assign 1 and 4.
Other than that, there are no restrictions.

Answer 9

How did you get 16?

Answer 10

https://db.tt/l07ownYm

Answer 11

I don't know if this is the correct way of showing an automorphism

Answer 12

What you did doesn't make sense. Suppose your function would do f(1) = 2. Then we have to let f(2)=1.

Answer 13

I'm not sure what nodes you are swapping with what...

Answer 14

An automorphism is a function which maps each node to a new node, but maintains adjacency, roughly speaking. Correct?

Answer 15

yeah

Answer 16

If there were no edges, then we could say the number of automophisms is \(|V|^2\), and this is the maximum number since we don't have any extra restrictions when we don't have any edges.

Answer 17

Whoops, that isn't actually correct either...

Answer 18

The maximum automorphisms, which no edge restrictons, would just be \(|V|!\) since we're just permuting vertices...

Answer 19

Does that make sense?

Answer 20

I think so

Answer 21

So we know it has to be between \(1\) and \(4!=24\)

Answer 22

When n=2
V={1,2,3,4}
E={(1,2),(3,4)}

We can let 1 be 1 or 2. But 2 must then be the other.

Answer 23

So for 1, we can pick 4 ways to pick it.
This decision forces us to pick a certain node for 2, basically it means there will only be one way to pick 2.

For 3, we have 2 remaining nodes to pick.
for 4, just like 2, we have only one way to pick it.

Answer 24

Hmm, 4*1*2*1=8

Answer 25

that makes sense to me, but I'm still having a little trouble with the definition itself. Does it need to maintain the shape of the original graph? For example can I create cross edges like I did?

Answer 26

If I keep the same shape I get 8 automorphisms when n=2

Answer 27

Well, the best way to write an automorphism is to list the vertices, then write the vertice they are mapped to next to them.

Answer 28

ok this is getting more clear

Answer 29

so write a table
```
V | f(V)
1 | 2
2 | 1
3 | 3
4 | 4
```

Answer 30

https://db.tt/g9SGYNPC

Answer 31

ok I think this makes sense

Answer 32

The next step is to list each edge as \((v_1,v_2)\) and making sure that \((f(v_1),f(v_2))\) is still in the list.

Answer 33

For example
```
E | f(E)
(1,2) | (2,1)
(3,4) | (3,4)
```

Answer 34

I think all the graphs this creates are just more and more lines with 2 vertices. There will be n of them I think. The first line can map in 2 ways to n lines. The next can map in 2 ways to n-1 lines and so on. So maybe there are 2*n! ways?

Answer 35

Just a thought I had

Answer 36

But 2*2! = 4, but we want 8 when n=2.

Answer 37

hmm you're right. That's not quite right.

Answer 38

I think I have the answer already.

Answer 39

Is my thinking close at all?

Answer 40

or is there another way of going about this?

Answer 41

Your thinking is a start, but it isn't really close to an answer.

Answer 42

The way you should be thinking about this is as follows...
We have 2n nodes.

How many ways do we assign node 1?
How many ways do we assign node 2?
etc.

Answer 43

there are 2n ways to assign node 1
there is 1 way to assign node 2

there are 2n-1 ways to assign node 3
there is one way to assign node 4

so half the choices are one choice. So we want a factorial type thing on 2n where it goes down by 2 each time

Answer 44

There isn't 2n-1 ways to assign node 3, since 1 and 2 were already assigned.

Answer 45

oh right 2n-2 ways of assigning node 3

Answer 46

We have:
\[
(2n)(2n-2)(2n-4)...(2) = (2\times n)(2\times (n-1))...(2\times 1)
\]

Answer 47

(2n)(2n-2)(2n-4)(2n-6)...
2(n)(n-1)(n-2)(n-3)...

looks like 2(n!) again

Answer 48

\[
=\underbrace{2\times 2\times \ldots \times 2}_{n}\times n! = 2^nn!
\]

Answer 49

oooh

Answer 50

I made a mistake factoring out the 2

Answer 51

It's kinda lame, but it turns out that \(2^nn! = n!!\)
I say lame because \(n!!\neq (n!)!\) due to this definition.

Answer 52

Whoops, I said that wrong... \[
n!! = n(n-2)(n-4)\dots (2)
\]So when \(n\) is even, we can say: \[
n!! = 2^{n/2}(n/2)!
\]

Answer 53

So basically \(2^nn! = (2n)!!\).
Regardless, the answer is probably best left at \(2^nn!\)

Answer 54

You could also write it as: \[
\prod_{i=1}^{n}2i
\]

Answer 55

\[
\prod_{i=1}^{n}2i = \left(\prod_{i=1}^{n}2\right)\left(\prod_{i=1}^{n}i \right) = (2^n)(n!)=2^nn!
\]

Answer 56

ok thank you very very much for helping me on this

Answer 57

I was pretty stuck on it

Answer 58

would you mind possibly helping my on just one more?

Answer 59

I suppose.

Answer 60

Let G be a graph on 5 verticies. Show that it is not possible for every vertex to have degree 3

Answer 61

where the degree is the number of edges incident with a vertex

Answer 62

when I try to do it I can't make it work. I just don't really know why it's happening

Answer 63

oh I think I've got it!

Answer 64

ok

Answer 65

I have a theorem that states\[\sum_{v \in( G )}^{} \deg(v) = 2|E(G)|\]
since each edge has 2 ends and when we sum the degrees we are counting each edge twice once for each edge.

Given that this is true. If we assume that the degree of each vertex is 3 then the sum is 15.

This gives us that 15 =2|E(G)| which is a contradiction because 15 is not a multiple of 2.

Answer 66

That makes sense.

Answer 67

woo thanks so much for helping me! I really really appreciate it!