Talk:Petersen graph

From Wikipedia, the free encyclopedia

This article is within the scope of WikiProject Mathematics.
Mathematics grading:	B Class	High Importance	Field: Discrete mathematics
Lists need more prose to accompany them. Tompw (talk) 15:36, 4 January 2007 (UTC)

I took out

"Although it appears to contain a subgraph homomorphic to K₅, it doesn't; however, it does contain a subgraph homomorphic to K_3,3."

which is wrong. The Petersen graph has both as minors.

"I'm not just talking to my hat here"; well, I am. Anyway, The Petersen Graph by D. A. Holton and J. Sheehan has a lot of info that should go here. dbenbenn | talk 05:30, 19 Mar 2005 (UTC)

It can be added some pseudocode to create the graph, or a list of its arcs.

[edit] change needed in comments about (3,5) cage

I tried to make the following change on August 9, but I wasn't able to save the change. Concerning (3,5) cage, the Wiki should say

• has the least number of vertices of any cubic graph of girth 5; thus it is a (3,5)-cage graph (in fact, it is the only such); also it is the only (3,5)-Moore graph.

I will try to make the change later.

I noticed that the statment given was wrong, because I was looking at a picture of the dodecahedron, which is another connected cubic graph of girth 5.

Good catch!

I've taken out the statement that the Petersen graph is "the unique (3,5)-Moore graph". This comes from MathWorld, but according to their definition of Moore graph, a (3,5)-Moore graph is a degree-3 graph of girth 5 with the maximum number of nodes. But the dodecahedron is degree 3, girth 5, and has 20 nodes. I'm confused. dbenbenn | talk 08:41, 8 October 2005 (UTC)

And now I put it back in. Apparently a (v,g)-Moore graph is a v-regular graph of girth g that achieves the naive lower bound on the number of vertices. (Pick a vertex. It has v neighbors; there are v(v − 1) vertices at distance two, v(v − 1)² at distance 3, etc.) dbenbenn | talk 15:00, 23 October 2005 (UTC)

[edit] Three crossings

I removed this embedding of the Petersen graph from the article. Note that there are infinitely many embeddings of the graph. How is this one significant? There's a link at the bottom of the article to Commons:Category:Petersen graph, which I think is sufficient unless this embedding has some interesting property. Also, the caption displays a lack of understanding. dbenbenn | talk 20:39, 15 October 2005 (UTC)

Of course this one is not significant itself. There are three images currently in the article. They all 'look alike' and I've put this version of Petersen graph, which does not look like the first, and best known embedding. What is wrong with the caption? The article also does not talk about graph isomorphism explicitly, so I believe this image can complement it. --xJaM 10:20, 20 October 2005 (UTC)

The Petersen graph is hypo-Hamiltonian: by deleting any vertex, the remaining graph is Hamiltonian.

The three images don't "look alike". The first is the standard embedding. The second proves that the crossing number is 2, a fact mentioned in the text. The third proves it's a unit-distance graph, another fact mentioned in the text. It might be worth adding Image:Petersen graph 2.svg, which proves the graph is hypo-Hamiltonian ... dbenbenn | talk 20:45, 4 December 2005 (UTC)