Mixing
Why is the Petersen graph no Cayley graph?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
On the Wikipedia page of the Petersen graph it is mentioned that it is not a Cayley graph.
How it this proved?
Honestly I don't even know how to start this. The only criteria I can think of is that all vertices must have the same degree. Also the degree being odd should imply that one generator of the group has order 2. But then how do I proceed?
Edit: As already mentioned in the comments, the link did not answer my question.
abstract-algebra group-theory graph-theory geometric-group-theory cayley-graphs
asked Jul 16 at 16:43
stacky
557
 |Â
show 5 more comments
up vote
4
down vote
favorite
On the Wikipedia page of the Petersen graph it is mentioned that it is not a Cayley graph.
How it this proved?
Honestly I don't even know how to start this. The only criteria I can think of is that all vertices must have the same degree. Also the degree being odd should imply that one generator of the group has order 2. But then how do I proceed?
Edit: As already mentioned in the comments, the link did not answer my question.
abstract-algebra group-theory graph-theory geometric-group-theory cayley-graphs
asked Jul 16 at 16:43
stacky
557
I guess I shouldve used the search function
– stacky
Jul 16 at 16:50
It's a good question, if already asked: math.stackexchange.com/questions/348779/… - although the answer there could be improved. Basically it can only correspond to a small group, of which there are a limited number, and it doesn't so correspond.
– Joffan
Jul 16 at 16:55
1
@Joffan I took a look at the answer, but I dont really get it. It seems like a fact from group theory (which i have to accept) that there are only two groups with $10$ elements, These are $D_5$ and $mathbb Z_10$. It is clear to me that for the standard generating sets of these groups, the Cayley graphs differ. How can I see that there is NO generating set realising the graph?
– stacky
Jul 16 at 16:58
$C_10$ is cyclic so clearly not appropriate. $D_5$ has an order-2 element which should lead to even cycles on the graph, but Petersen has only odd (unlike say the pentagonal prism graph).
– Joffan
Jul 16 at 17:09
@Joffan ah, I see, in a different generating set the order 2 element would be a $n$-word. This would then give a $2n$-cycle. Why is the case $C_10$ "clear"?
– stacky
Jul 16 at 17:15
 |Â
show 5 more comments
up vote
4
down vote
favorite
up vote
4
down vote
favorite
On the Wikipedia page of the Petersen graph it is mentioned that it is not a Cayley graph.
How it this proved?
Honestly I don't even know how to start this. The only criteria I can think of is that all vertices must have the same degree. Also the degree being odd should imply that one generator of the group has order 2. But then how do I proceed?
Edit: As already mentioned in the comments, the link did not answer my question.
abstract-algebra group-theory graph-theory geometric-group-theory cayley-graphs
asked Jul 16 at 16:43
stacky
557
On the Wikipedia page of the Petersen graph it is mentioned that it is not a Cayley graph.
How it this proved?
Honestly I don't even know how to start this. The only criteria I can think of is that all vertices must have the same degree. Also the degree being odd should imply that one generator of the group has order 2. But then how do I proceed?
Edit: As already mentioned in the comments, the link did not answer my question.
abstract-algebra group-theory graph-theory geometric-group-theory cayley-graphs
asked Jul 16 at 16:43
stacky
557
edited Jul 16 at 17:11
asked Jul 16 at 16:43
stacky
557
asked Jul 16 at 16:43
stacky
557
asked Jul 16 at 16:43
stacky
557
557
I guess I shouldve used the search function
– stacky
Jul 16 at 16:50
It's a good question, if already asked: math.stackexchange.com/questions/348779/… - although the answer there could be improved. Basically it can only correspond to a small group, of which there are a limited number, and it doesn't so correspond.
– Joffan
Jul 16 at 16:55
1
@Joffan I took a look at the answer, but I dont really get it. It seems like a fact from group theory (which i have to accept) that there are only two groups with $10$ elements, These are $D_5$ and $mathbb Z_10$. It is clear to me that for the standard generating sets of these groups, the Cayley graphs differ. How can I see that there is NO generating set realising the graph?
– stacky
Jul 16 at 16:58
$C_10$ is cyclic so clearly not appropriate. $D_5$ has an order-2 element which should lead to even cycles on the graph, but Petersen has only odd (unlike say the pentagonal prism graph).
– Joffan
Jul 16 at 17:09
@Joffan ah, I see, in a different generating set the order 2 element would be a $n$-word. This would then give a $2n$-cycle. Why is the case $C_10$ "clear"?
– stacky
Jul 16 at 17:15
 |Â
show 5 more comments
I guess I shouldve used the search function
– stacky
Jul 16 at 16:50
It's a good question, if already asked: math.stackexchange.com/questions/348779/… - although the answer there could be improved. Basically it can only correspond to a small group, of which there are a limited number, and it doesn't so correspond.
– Joffan
Jul 16 at 16:55
1
@Joffan I took a look at the answer, but I dont really get it. It seems like a fact from group theory (which i have to accept) that there are only two groups with $10$ elements, These are $D_5$ and $mathbb Z_10$. It is clear to me that for the standard generating sets of these groups, the Cayley graphs differ. How can I see that there is NO generating set realising the graph?
– stacky
Jul 16 at 16:58
$C_10$ is cyclic so clearly not appropriate. $D_5$ has an order-2 element which should lead to even cycles on the graph, but Petersen has only odd (unlike say the pentagonal prism graph).
– Joffan
Jul 16 at 17:09
@Joffan ah, I see, in a different generating set the order 2 element would be a $n$-word. This would then give a $2n$-cycle. Why is the case $C_10$ "clear"?
– stacky
Jul 16 at 17:15
I guess I shouldve used the search function
– stacky
Jul 16 at 16:50
I guess I shouldve used the search function
– stacky
Jul 16 at 16:50
It's a good question, if already asked: math.stackexchange.com/questions/348779/… - although the answer there could be improved. Basically it can only correspond to a small group, of which there are a limited number, and it doesn't so correspond.
– Joffan
Jul 16 at 16:55
It's a good question, if already asked: math.stackexchange.com/questions/348779/… - although the answer there could be improved. Basically it can only correspond to a small group, of which there are a limited number, and it doesn't so correspond.
– Joffan
Jul 16 at 16:55
1
1
@Joffan I took a look at the answer, but I dont really get it. It seems like a fact from group theory (which i have to accept) that there are only two groups with $10$ elements, These are $D_5$ and $mathbb Z_10$. It is clear to me that for the standard generating sets of these groups, the Cayley graphs differ. How can I see that there is NO generating set realising the graph?
– stacky
Jul 16 at 16:58
@Joffan I took a look at the answer, but I dont really get it. It seems like a fact from group theory (which i have to accept) that there are only two groups with $10$ elements, These are $D_5$ and $mathbb Z_10$. It is clear to me that for the standard generating sets of these groups, the Cayley graphs differ. How can I see that there is NO generating set realising the graph?
– stacky
Jul 16 at 16:58
$C_10$ is cyclic so clearly not appropriate. $D_5$ has an order-2 element which should lead to even cycles on the graph, but Petersen has only odd (unlike say the pentagonal prism graph).
– Joffan
Jul 16 at 17:09
$C_10$ is cyclic so clearly not appropriate. $D_5$ has an order-2 element which should lead to even cycles on the graph, but Petersen has only odd (unlike say the pentagonal prism graph).
– Joffan
Jul 16 at 17:09
@Joffan ah, I see, in a different generating set the order 2 element would be a $n$-word. This would then give a $2n$-cycle. Why is the case $C_10$ "clear"?
– stacky
Jul 16 at 17:15
@Joffan ah, I see, in a different generating set the order 2 element would be a $n$-word. This would then give a $2n$-cycle. Why is the case $C_10$ "clear"?
– stacky
Jul 16 at 17:15
 |Â
show 5 more comments
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
$G = C_10$ is abelian, and so if $a$ and $b$ are two of the generators in the Cayley graph then $a^-1b^-1ab$ gives a cycle of length $4$, but the Petersen graph has none such.
So suppose that $G= D_10$. As you say, at least one of the generators, say $a$ must have order $2$. If there is a generator $b$ of order $5$, then $(ab)^2 = 1$, so again we should have a cycle of length $4$, but there is none.
The only other possibility is that all generators have order $2$, but then there is no product of $5$ generators equal to the identity. But the Petrsen graph does have $5$-cycles, contradiction.
answered Jul 16 at 17:17
Derek Holt
49.7k53366
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
$G = C_10$ is abelian, and so if $a$ and $b$ are two of the generators in the Cayley graph then $a^-1b^-1ab$ gives a cycle of length $4$, but the Petersen graph has none such.
So suppose that $G= D_10$. As you say, at least one of the generators, say $a$ must have order $2$. If there is a generator $b$ of order $5$, then $(ab)^2 = 1$, so again we should have a cycle of length $4$, but there is none.
The only other possibility is that all generators have order $2$, but then there is no product of $5$ generators equal to the identity. But the Petrsen graph does have $5$-cycles, contradiction.
answered Jul 16 at 17:17
Derek Holt
49.7k53366
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
add a comment |Â
up vote
6
down vote
accepted
$G = C_10$ is abelian, and so if $a$ and $b$ are two of the generators in the Cayley graph then $a^-1b^-1ab$ gives a cycle of length $4$, but the Petersen graph has none such.
So suppose that $G= D_10$. As you say, at least one of the generators, say $a$ must have order $2$. If there is a generator $b$ of order $5$, then $(ab)^2 = 1$, so again we should have a cycle of length $4$, but there is none.
The only other possibility is that all generators have order $2$, but then there is no product of $5$ generators equal to the identity. But the Petrsen graph does have $5$-cycles, contradiction.
answered Jul 16 at 17:17
Derek Holt
49.7k53366
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
$G = C_10$ is abelian, and so if $a$ and $b$ are two of the generators in the Cayley graph then $a^-1b^-1ab$ gives a cycle of length $4$, but the Petersen graph has none such.
So suppose that $G= D_10$. As you say, at least one of the generators, say $a$ must have order $2$. If there is a generator $b$ of order $5$, then $(ab)^2 = 1$, so again we should have a cycle of length $4$, but there is none.
The only other possibility is that all generators have order $2$, but then there is no product of $5$ generators equal to the identity. But the Petrsen graph does have $5$-cycles, contradiction.
answered Jul 16 at 17:17
Derek Holt
49.7k53366
$G = C_10$ is abelian, and so if $a$ and $b$ are two of the generators in the Cayley graph then $a^-1b^-1ab$ gives a cycle of length $4$, but the Petersen graph has none such.
So suppose that $G= D_10$. As you say, at least one of the generators, say $a$ must have order $2$. If there is a generator $b$ of order $5$, then $(ab)^2 = 1$, so again we should have a cycle of length $4$, but there is none.
The only other possibility is that all generators have order $2$, but then there is no product of $5$ generators equal to the identity. But the Petrsen graph does have $5$-cycles, contradiction.
answered Jul 16 at 17:17
Derek Holt
49.7k53366
answered Jul 16 at 17:17
Derek Holt
49.7k53366
answered Jul 16 at 17:17
Derek Holt
49.7k53366
answered Jul 16 at 17:17
Derek Holt
49.7k53366
49.7k53366
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
add a comment |Â
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
Thx for your answer. What do you mean with "the other possibility". Do you refer to another group with 10 elements in this part? Also, why do you say "at least one of the generators must have order 2". Its clear that there are elements of order 2, but why must I take such an element as a generator?
– stacky
Jul 16 at 17:24
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
The third paragraph is still assuming $G = D_10$ (which is confusingly often denoted by $D_5$). By "the only other possibility" I meant that if there is no generator of order $5$, then all of the generators must have order $2$. As you said yourself, the fact that the degree is odd implies that at least one of the generators has order $2$.
– Derek Holt
Jul 16 at 17:28
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
Sorry, but why is $(ab)^2=1$?
– stacky
Jul 16 at 17:36
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
In dihedral groups the product of a rotation and a reflection is a reflection.
– Derek Holt
Jul 16 at 18:10
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
ah, it comes from the explicit group structure. Thx
– stacky
Jul 16 at 18:20
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853588%2fwhy-is-the-petersen-graph-no-cayley-graph%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I guess I shouldve used the search function
– stacky
Jul 16 at 16:50
It's a good question, if already asked: math.stackexchange.com/questions/348779/… - although the answer there could be improved. Basically it can only correspond to a small group, of which there are a limited number, and it doesn't so correspond.
– Joffan
Jul 16 at 16:55
1
@Joffan I took a look at the answer, but I dont really get it. It seems like a fact from group theory (which i have to accept) that there are only two groups with $10$ elements, These are $D_5$ and $mathbb Z_10$. It is clear to me that for the standard generating sets of these groups, the Cayley graphs differ. How can I see that there is NO generating set realising the graph?
– stacky
Jul 16 at 16:58
$C_10$ is cyclic so clearly not appropriate. $D_5$ has an order-2 element which should lead to even cycles on the graph, but Petersen has only odd (unlike say the pentagonal prism graph).
– Joffan
Jul 16 at 17:09
@Joffan ah, I see, in a different generating set the order 2 element would be a $n$-word. This would then give a $2n$-cycle. Why is the case $C_10$ "clear"?
– stacky
Jul 16 at 17:15