Talk:Petersen graph

WikiProject Mathematics (Rated B-class, Mid-importance)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
 B Class
 Mid Importance
Field: Discrete mathematics

homomorphisms

I took out

"Although it appears to contain a subgraph homomorphic to K5, it doesn't; however, it does contain a subgraph homomorphic to K3,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)

• The redacted statement is backwards. Only a bipartite graph can be homomorphic to a bipartite graph, e.g. to $K_{3,3}$. Any 5-colourable graph is homomorphic to $K_5$. In any case, a graph 'G' having 'H' as a minor does not imply that 'G' is homomorphic to 'H', nor does the latter imply the former. Basically with a homomorphism you can add edges freely, and with a minor you can remove edges freely. Adking80 (talk) 14:06, 9 December 2008 (UTC)

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)^2$ at distance 3, etc.) dbenbenn | talk 15:00, 23 October 2005 (UTC)

Three crossings

File:Petersen graph, three crossings.png
The Petersen graph with three crossings. Image clearly shows how this Petersen graph is isomorphic to first one.

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)

Nonhamiltonian cubic graphs

The article says:

It is the smallest bridgeless cubic graph with no Hamiltonian cycle.

Is "bridgeless" necessary here? I thought that the Petersen graph was the smallest cubic nonhamiltonian graph. -- Dominus (talk) 18:13, 4 February 2008 (UTC)

There's an equally small nonhamiltonian cubic graph with one bridge, having five vertices on each side of the bridge. Also, having a bridge is an obvious obstacle to being hamiltonian so it's harder to find bridgeless nonhamiltonian graphs. —David Eppstein (talk) 18:30, 4 February 2008 (UTC)

Generalized Petersen Graphs

I'm no graph theorist, but isn't the definition of the edges wrong? Should it be v_i v_{i+k} instead of v_i u_{i+k} ? —Preceding unsigned comment added by 92.50.106.233 (talk) 08:17, 30 April 2008 (UTC)

Yes. Fixed. —David Eppstein (talk) 14:19, 30 April 2008 (UTC)

The number of spanning trees

Anonymous editors with three IP addresses have been attempting recently to change the article to say that the Petersen graph has 2400 spanning trees, rather than 2000 as our article (following its reference arxiv:math.CO/9907050) formerly said. One of the anonymous edits claimed that the 2400 number comes from a calculation done by Jungnickel at Augsburg. In order to verify for myself the truth of this matter, I wrote the following code, which agrees with the earlier 2000 number. Unless someone convincingly explains why both my code and the reference are incorrect, I intend to continue reverting this change. —David Eppstein (talk)

```# Python code to count spanning trees of the Petersen graph
# D. Eppstein, July 26, 2008

# Define the edges of the Petersen graph
Edges = [(i,(i+1)%5) for i in range(5)] + \
[(i,i+5) for i in range(5)] + \
[(i+5,(i+2)%5+5) for i in range(5)]

# Remove one leaf from a list of edges and return the remaining edges
def RemoveLeaf(Tree):
for v in range(10):
neighborhood = [e for e in Tree if v in e]
if len(neighborhood) == 1:
T = list(Tree)
T.remove(neighborhood[0])
return T
return Tree

# It's a forest iff it can be reduced to nothing by removing leaves,
# and a spanning tree iff it is a forest with sufficiently many edges.
def IsSpanningTree(x):
Tree = [Edges[i] for i in range(15) if x & (1<<i)]
if len(Tree) != 9:
return False    # Wrong number of edges to be a tree
for i in range(9):
Tree = RemoveLeaf(Tree)
if Tree:
return False    # Couldn't remove leaves all the way to nothing
return True

# Test all subsets of edges
count = 0
for x in range(1<<15):
if IsSpanningTree(x):
count += 1

print "The Petersen graph has",count,"spanning trees."
```

The eigenvalues of the adjacency matrix are 3 (once), 1 (5 times), -2 (4 times). Therefore 10 times the number of spanning trees is 2554=20000. So 2000 is correct. McKay (talk) 03:20, 27 July 2008 (UTC)

Hamiltonian

I think that part of the paragraph has been lifted from Mathworld. This should probably be investigated. http://mathworld.wolfram.com/PetersenGraph.html —Preceding unsigned comment added by 131.111.29.216 (talk) 15:59, 1 November 2008 (UTC)

This section is perhaps overly confusing, especially the explanation of why it is not Hamiltonian. Unfortunately I am no expert in this or I would update it myself, http://oneweb.utc.edu/~Christopher-Mawata/petersen2/petham.htm perhaps an argument in this style would be easier for a layman to follow. 81.108.18.30 (talk) 08:47, 29 May 2009 (UTC)

I'm interested in the following characterization:

• has radius 2 and diameter 2. It is the largest cubic graph with diameter 2.
It's easy enough to prove, but I added a reference. —David Eppstein (talk) 16:14, 12 April 2010 (UTC)

What I am not understanding is why it is stated that the graph is 4-chromatic when we have a picture that clearly show a chromatic index of 3... —Preceding unsigned comment added by 87.202.65.168 (talk) 03:29, 7 January 2011 (UTC)

It's stated that it has chromatic index 4, but the chromatic index is not the same as the chromatic number (which in this case is 3). Chromatic index is edge-coloring number, chromatic number is vertex-coloring number. —David Eppstein (talk) 03:43, 7 January 2011 (UTC)

Symmetry group

I think the symmetry group of this graph is the alternating group A5, not S5. Any symmetry can be described (using the standard picture) by describing

1. where the top vertex is moved to (10 choices)
2. where the vertex immediately below the top vertex goes to (3 choices)
3. where either of the two other vertices connected to the top vertex goes (2 choices).

Total: 60 choices, not 120. If so then the Wikipedia page for Algebraic graph theory needs changing too. Regards AlHutchins (talk) 12:30, 23 January 2011 (UTC)

PS Please forget this. I have just realised there is another choice to be made. AlHutchins (talk) 13:55, 23 January 2011 (UTC)