The last week I started to solve problems from an old russian collection of problems, but have stick on these 4:

1) Prove(formal) that Petersen graph has chromatic number 3(meaning that its vertices can be colored with three colors).

2) Prove(formal) that Petersen graph has a Hamiltonian path.

3) Does the Petersen graph has an Eulerian path(prove your opinion)?

4) For Petersen graph- prove that any set of five elemental vertices induced subgraph with at least one edge.

I've an idea for the first 3, but don't know how to prove them formal...


(4) seems to be asking for a proof of:

Any $5$-vertex induced subgraph of the Petersen graph contains an edge.

This essentially asks for the size of the largest independent set. A formal proof of this would consist of computing all $\binom{10}{5}$ such induced subgraphs and observing that they have an edge. I'll give a more mathematician-friendly proof below.

We can interpret the Petersen graph as a Kneser graph; the vertices are $2$-subsets of $\{1,2,3,4,5\}$ and the edges are between disjoint subsets. This is depicted below:

Petersen graph/Kneser graph

If we take an independent sets of size $k$ of the Petersen graph, we can draw it as a $k$-edge subgraph of $K_5$ (on the vertex set $\{1,2,3,4,5\}$). For example, the independent set of size $4$ given by $$\big\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\big\}$$ corresponds to the subgraph

Independent set of size 4

of $K_5$.

Claim: An independent set of size $k$ of the Petersen graph is equivalent to a $k$-edge subgraph of $K_5$ for which each edge shares an endpoint with every other edge.

If two edges existed in the subgraph of $K_5$ which do not share an endpoint, e.g. $12$ and $34$, they would correspond to two vertices of the Petersen graph joined by an edge (i.e., not an independent set), $\{1,2\}$ and $\{3,4\}$ in our example.

To complete the proof, we need to show there are no $5$-edge subgraphs $H$ of $K_5$ that satisfy the claim.

To begin with, we observe that $H$ contains a cycle (since acyclic graphs on $n$ vertices must have $n-1$ or fewer edges). If $H$ contains a $4$-cycle or a $5$-cycle, then the claim is not satisfied. Hence $H$ contains a $3$-cycle.

Suppose $a,b,c$ are the vertices of the $3$-cycle, and $uv$ is an edge in $H$ not in this triangle. One of the following must be true:

  • $u=a$, in which case $v \in \{b,c\}$ (otherwise $uv$ and $bc$ do not share an endpoint), contradicting the assumption that $uv$ does not belong to the $3$-cycle. (Similarly for $u=b$ and $u=c$.)
  • $u \not\in \{a,b,c\}$, in which case, the claim implies $v \in \{a,b\}$, $v \in \{a,c\}$ and $v \in \{b,c\}$, which is impossible, giving a contradiction.

We conclude that the Petersen graph has no $5$-vertex independent sets.

  • $\begingroup$ Thanks for the fully answer but we must prove the problem(not to disprove it)...or maybe the requirement is not right? $\endgroup$ – DiscreteMath'sFan Jan 3 '13 at 4:55
  • $\begingroup$ p.s. They are asking for a proof of that any 5 set of vertices of a Petersen graph induced a subgraph with at least one edge. $\endgroup$ – DiscreteMath'sFan Jan 3 '13 at 5:11
  • $\begingroup$ Yes, that's what I've shown. $\endgroup$ – Douglas S. Stones Jan 4 '13 at 7:17
  • $\begingroup$ At Douglas S. Stones - could you explain what do you mean of "4-cycle" - cycle width lenght 4?... my English is very bad $\endgroup$ – DiscreteMath'sFan Jan 4 '13 at 12:13
  • $\begingroup$ A 4-cycle is drawn here, which is my answer to another question. $\endgroup$ – Douglas S. Stones Jan 4 '13 at 12:25

For 1 you can exhibit a specific valid 3-colouring and note that a graph containing an odd cycle cannot be 2-coloured.

Similarly, you need only exhibit an explicit Hamiltonian path for 2).

What is your opinion for 3? EDIT: After your comment, you seem to have proved that there is no Euler path. Indeed, probably you had a theorem that a graph $G$ admits an Euler path iff $G$ is connected and has $\le 2$ odd vertices. Thus if you prove that the Petersen graph has $10>2$ odd vertices, you are done.

(And actually, I don't really understand 4)

  • 1
    $\begingroup$ I think 4 says that the largest independent set is of size 4. $\endgroup$ – Peter Taylor Jan 2 '13 at 19:11
  • $\begingroup$ Thank's for the fast response. For 3 - I think that it doesn't have an Eulerian path because not all vertices are of an even degree... $\endgroup$ – DiscreteMath'sFan Jan 2 '13 at 19:12
  • $\begingroup$ 1)I do it exactly the same but the lecture says that this method is not a formal prove 2) for two - i didn't understand what do you mean :( 4) me too :D $\endgroup$ – DiscreteMath'sFan Jan 2 '13 at 19:16
  • $\begingroup$ Any other ideas? $\endgroup$ – DiscreteMath'sFan Jan 2 '13 at 19:24
  • $\begingroup$ Why do you think that the method described for 1 is not formal? What kind of argument are you looking for? $\endgroup$ – Eric Stucky Jan 3 '13 at 0:12

You can choose at most 2 vertices from the inner pentagram, and at most 2 vertices from the outer pentagon. On the other hand, we can easily construct an independent set of size 4.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.