Why petersen graph is not hamiltonian

It is impossible to connect any vertex to v5. This is because if we connect any vertex to v5, it will result in a 3-cycle or 4-cycle.

Example, Suppose we connect v5 and v9, it will make a 4-cycle v5 — v9 — v0 — v4 — v5. Suppose we connect v5 and v1, it will make a 4-cycle v5 — v1 — v0 — v4 — v5. Basically connecting any vertex to v5 will result in 3-cycle or 4-cycle which contradicts the fact that Petersen Graph does not contain any 3-cycle or 4-cycle.

Therefore, our assumption that the Petersen Graph contains a Hamiltonian circuit is contradictory. Thus, we can say that the Petersen Graph does not contain a Hamiltonian circuit. In other words, Petersen Graph is not Hamiltonian. Rosen Petersen Graph. This answer is more readable for a beginner because it spells out what is going on more explicitly in contrast to Gerry's answer.

The latter is perfectly fine for people who are more familiar with graph theory proofs. Sign up or log in Sign up using Google.

Sign up using Facebook. Sign up using Email and Password. Post as a guest Name. Email Required, but never shown. Upcoming Events. Featured on Meta. Now live: A fully responsive profile. The unofficial elections nomination post. Linked 2. Related 2. Hot Network Questions. Let us consider the extra edge incident to ; the others are equivalent. Since the Petersen graph has no loops or multiple edges, this edge cannot go from to itself, or to or. More specifically, we cannot we cannot have an edge from to or , as these make triangles, as in the dashed edges below:.

And we cannot have edges to or to , as these make 4 cycles:. So for instance, can only be connected to or with its extra edge. If not, then every extra edge would skip 5 vertices. Since each vertex has degree 3, there must be one extra edge through each of these vertices, connecting to the opposite vertex. But this configuration has many four cycles — for instance,. Since the Petersen graph does not have any 4 cycles, we see this cannot occur:.

Relabeling our edges if necesary, we can make the extra edge that skips the 4 cycle be the edge. Now, consider the extra edge at. This cannot skip 5, because that would make it adjacent to , which already has its extra edge. Thus, it must skip 4, and be adjacent to either or. But since each of these are adjacent to , it would create a 4-cycle: either , or.

We have drawn the edge from to in solid red; any of the dashed edges from create a configuration not found in the Petersen graph:.