[Math] Petersen graph prolems

Question

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…

Answer 1

(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.