Talk:Petersen graph

homomorphisms

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)

• 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)

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)

"The second proves that the crossing number is 2." I don't think, that's true. It only shows, that the crossing number of the Petersen graph is at most 2. Since the Petersen graph is not planar, we also know its crossing number is at least 1. So why is it 2 and not 1? Did I miss an argument in the article? — Preceding unsigned comment added by Rkw95 (talk • contribs) 14:12, 21 April 2018 (UTC)

The quick argument is: because it's nonplanar it has at least one crossing. Now remove one of the crossing edges; the remaining graph is a subdivision of K_3,3, still nonplanar, so there is at least one more crossing. —David Eppstein (talk) 17:40, 21 April 2018 (UTC)

Thank you very much, now I am convinced!

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)

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)

References Please

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 A₅, not S₅. 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)

Purpose .. application

But what's it good for?? — Preceding unsigned comment added by 60.242.61.222 (talk • contribs)

As the second sentence of the article says, "as a useful example and counterexample for many problems in graph theory". —David Eppstein (talk) 07:14, 10 November 2016 (UTC)