Since each vertex is labeled with a subset with two elements of $\{1,2,3,4,5\}$, then any permutation of $\{1,2,3,4,5\}$ is going to induce a permutation of the vertices. Moreover, if $\{a,b\}\cap\{c,d\}=\emptyset$, and $\sigma$ is a permutation of $\{1,2,3,4,5\}$, then $\{\sigma(a),\sigma(b)\}\cap\{\sigma(c),\sigma(d)\} = \emptyset$. That is: this permutation of the vertices sends adjacent vertices to adjacent vertices (and non-adjacent vertices to non-adjacent vertices).
Also, two permutations induce the same permutation of the vertices if and only if they are identical permutations (you should prove this). That means that every element of $S_5$ induces a distinct automorphism of the graph.
Are these all the automorphisms, or are there more? If $\tau$ is any automorphism, then by composing with an appropriate permutation of $\{1,2,3,4,5\}$ you may assume that the map fixes $\{1,2\}$; that means that the vertices adjacent to $\{1,2\}$, $\{3,4\}$, $\{3,5\}$, and $\{4,5\}$, must map to each other. Composing with an appropriate permutation (that fixes $1$ and $2$) you may assume that the permutation also fixes $\{3,4\}$; and composing again by a suitable permutation, you can make it fix also $\{3,5\}$ $\{4,5\}$ (again, you need to prove this). So then you are left with an automorphism that fixes $\{1,2\}$ and its three neighbors. If you can show that this is also given by a permutation of $\{1,2,3,4,5\}$, then you will have shown that every automorphism "comes" from an element of $S_5$ (since composing with suitable automorphism that do give you the identity).
(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.
Best Answer
To confirm a graph is isomorphic to Petersen; then I'd find a five-cycle in it and label it as $A_1A_2A_3A_4A_5A_1$. I'd let $B_1,\ldots,B_5$ be the other vertices adjacent to $A_1,\ldots,A_5$ respectively. If these are joined up as $B_1B_3B_5B_2B_4B_1$ then the graph is Petersen.