Talk:Petersen graph

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.

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)^{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 2⁵5⁴=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)