# Petersen graph prolems

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? –  DiscreteMath'sFan Jan 3 '13 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. –  DiscreteMath'sFan Jan 3 '13 at 5:11
Yes, that's what I've shown. –  Douglas S. Stones Jan 4 '13 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 –  DiscreteMath'sFan Jan 4 '13 at 12:13
A 4-cycle is drawn here, which is my answer to another question. –  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)

-
I think 4 says that the largest independent set is of size 4. –  Peter Taylor Jan 2 '13 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... –  DiscreteMath'sFan Jan 2 '13 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 –  DiscreteMath'sFan Jan 2 '13 at 19:16
Any other ideas? –  DiscreteMath'sFan Jan 2 '13 at 19:24
Why do you think that the method described for 1 is not formal? What kind of argument are you looking for? –  Eric Stucky Jan 3 '13 at 0:12