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...
 A: (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.
A: 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)
A: 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.
