# Petersen graph problems

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:

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

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.

• Thanks for the fully answer but we must prove the problem(not to disprove it)...or maybe the requirement is not right? Commented Jan 3, 2013 at 4:55
• 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. Commented Jan 3, 2013 at 5:11
• Yes, that's what I've shown. Commented Jan 4, 2013 at 7:17
• At Douglas S. Stones - could you explain what do you mean of "4-cycle" - cycle width lenght 4?... my English is very bad Commented Jan 4, 2013 at 12:13
• A 4-cycle is drawn here, which is my answer to another question. Commented Jan 4, 2013 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)

• I think 4 says that the largest independent set is of size 4. Commented Jan 2, 2013 at 19:11
• 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... Commented Jan 2, 2013 at 19:12
• 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 Commented Jan 2, 2013 at 19:16
• Any other ideas? Commented Jan 2, 2013 at 19:24
• Why do you think that the method described for 1 is not formal? What kind of argument are you looking for? Commented Jan 3, 2013 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.