Petersen graph problems

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.

Answer 2

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)

Answer 3

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.