{"id":1702,"date":"2015-07-01T01:00:44","date_gmt":"2015-07-01T01:00:44","guid":{"rendered":"http:\/\/blogs.ams.org\/visualinsight\/?p=1702"},"modified":"2016-10-13T23:03:35","modified_gmt":"2016-10-13T23:03:35","slug":"petersen-graph","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/visualinsight\/2015\/07\/01\/petersen-graph\/","title":{"rendered":"Petersen Graph"},"content":{"rendered":"
\n
\"Petersen<\/a>

Petersen Graph – Japheth Wood<\/p><\/div><\/div>\n

Suppose you have a set with 5 elements. There are 10 ways to choose a 2-element subset. Form a graph with these 10 choices as vertices, and with two vertices connected by an edge precisely when the corresponding subsets are disjoint. You get the graph shown here, called the Petersen graph<\/b><\/a>. <\/p>\n

The picture above, made by Japheth Wood<\/a>, also appears here:<\/p>\n

• Japheth Wood, Proof without words: the automorphism group of the Petersen graph is isomorphic to \\(\\mathrm{S}_5\\), Mathematics Magazine<\/i> 89<\/b> (October 2016), 267.<\/p>\n

As the title indicates, it’s easy to use this picture to determine the symmetry group of the Petersen graph.<\/p>\n

The Petersen graph is reputed to be a counterexample to many conjectures about graph theory, and it shows up in many places. We have described it as an example of a ‘Kneser graph’. The Kneser graph<\/b><\/a> \\(KG_{n,k}\\) is the graph whose vertices correspond to the \\(k\\)-element subsets of an \\(n\\)-element set, where two vertices are connected by an edge if and only if the two corresponding subsets are disjoint.<\/p>\n

We can also get the Petersen graph by taking a regular dodecahedron and identifying antipodal vertices and edges. <\/p>\n

Or, take the complete graph<\/a> on 5 vertices, \\(K_5\\), and form a new graph with the edges of \\(K_5\\) as vertices<\/i>, with two of these vertices connected by an edge if the corresponding edges in \\(K_5\\) do not<\/i> share a vertex. The result is the Petersen graph! We say the Petersen graph is the complement<\/a> of the line graph<\/a> of \\(K_5\\). <\/p>\n

For more details, see:<\/p>\n

• Wikipedia, Petersen graph<\/a>.<\/p>\n

The Petersen graph also shows up when you consider all possible phylogenetic trees that could explain how some set of species arose from a common ancestor. These are binary trees with a fixed number of leaves where each edge is labelled by a time in $[0,\\infty)$. The space of all such trees is contractible, but nonetheless topologically interesting. The space of phylogenetic trees with 4 leaves is the cartesian product of the cone on the Petersen graph and $[0,\\infty)^5$. For pictures illustrating this, see:<\/p>\n

• Louis Billera, Susan Holmes and Karen Vogtmann, Geometry of the space of phylogenetic trees<\/a>, Advances in Applied Mathematics<\/i> 27<\/b> (2001), 733-767.<\/p>\n

For related ideas, see<\/p>\n

• John Baez, Operads and the tree of life<\/a>.<\/p>\n

Here is another picture illustrating the relation between the Petersen graph and 2-element subsets of a 5-element set:<\/p>\n

\n
\"Petersen<\/a>

Petersen Graph – Tilman Piesk<\/p><\/div>\n<\/div>\n

The picture here is adapted from one that Tilman Piesk<\/a> created and put into the public domain on Wikicommons<\/a>.<\/p>\n

\n

Visual Insight<\/i> is a place to share striking images that help explain advanced topics in mathematics. I\u2019m always looking for truly beautiful images, so if you know about one, please drop a comment here<\/a> and let me know!<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

Suppose you have a set with 5 elements. There are 10 ways to choose a 2-element subset. Form a graph with these 10 choices as vertices, and with two vertices connected by an edge precisely when the corresponding subsets are disjoint. You get the graph shown here, called the Petersen graph<\/b><\/a>. <\/p>\n

<\/div>\n","protected":false},"author":66,"featured_media":2872,"comment_status":"open","ping_status":"closed","sticky":true,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[21,22,2],"tags":[],"class_list":["post-1702","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-combinatorics","category-graphs","category-images-library"],"jetpack_featured_media_url":"https:\/\/blogs.ams.org\/visualinsight\/files\/2015\/07\/petersen_graph_numbered.png","jetpack_shortlink":"https:\/\/wp.me\/p42Vmc-rs","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1702","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/users\/66"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/comments?post=1702"}],"version-history":[{"count":14,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1702\/revisions"}],"predecessor-version":[{"id":2874,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/posts\/1702\/revisions\/2874"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media\/2872"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/media?parent=1702"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/categories?post=1702"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/visualinsight\/wp-json\/wp\/v2\/tags?post=1702"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}