Show that Petersen Graph has no 7 cycle

Question

In order to prove that Petersen graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf

The given proof is

Suppose that the Petersen graph has a cycle C of length 7. Since any two vertices of C are connected by a path of length at most 3 on C, any additional edge with endpoints on C would create a cycle of length at most 4. Hence the third neighbor of each vertex on C is not on C. Thus there are seven edges from V(C) to the remaining three vertices. By the pigeonhole principle, one of the remaining vertices receives at least three of these edges. This vertex x not on C has three neighbors on C. For any three vertices on C, either two are adjacent or two have a common neighbor on C (again the pigeonhole principle applies). Using x, this completes a cycle of length at most 4. We have shown that the assumption of a 7-cycle leads to a contradiction.

I don't understand the part For any three vertices on C, either two are adjacent or two have a common neighbor on C (again the pigeonhole principle applies). Using x, this completes a cycle of length at most 4.

How can I show that part using pigeonhole principle.

Answer 1

We know that for any $3$ vertices on $C_7$ that either $2$ vertices are adjacent or $2$ vertices have a common neighbor on $C_7$. Since $C_7$ has no chords and every vertex on $C_7$ has degree $2$, then the remaining $3$ vertices not on $C_7$ ($x$, $y$, and $z$) are adjacent to distinct vertices on $C_7$. By the pigeonhole principle one of $3$ vertices, say $x$, is adjacent to $3$ vertices on $C_7$. However, this a contradiction since this implies that the Petersen graph contains a $3$-cycle or a $4$-cycle.

Answer 2

Let's assume $\exists$ a $C_7$ cycle in the Peterson Graph.
$\Longrightarrow$ Peterson Graph has total $10$ vertices. So, $3$ vertices are left.
$\Longrightarrow$ Each vertex on the Peterson Graph has degree $3$. So, each vertex in $V(C_7)$ still has one edge left to be incident on it.
$\Longrightarrow$ In the Peterson Graph $C_3$ or $C_4$ cycles are not possible. So, the edges left to be incident on the vertices of $C_7$ must be incident with vertices left i.e. $3$ vertices not there in the $C_7$.
$\Longrightarrow$ Now, see there are $7$ edges($1$ edge from each vertex of $C_7$) that needs to be incident with one of the $3$ vertices left.
Case-I: If we assume that there is no edge between these $3$ vertices then two out of the $3$ vertices will be incident with $3$ edges each(Since, each vertex in the Peterson Graph has degree $3$). We have $1$ edge and $1$ vertex left whose degree must be $3$.
Case-II: Since, Case-I is not possible. We must have an edge between $2$ vertices out of the $3$ left out vertices. Then, these $2$ vertices which are adjacent by this edge can have $2$ more edges incident from $C_7$ each. The remaining $1$ vertex will have to have $3$ edges incident from $C_7$ in this case. But we see all of these cases gives rise to $C_3$ or $C_4$ cycles which are not possible.
Case-III: Case-I and Case-II are False. But we also cannot have $2$ or more edges between these $3$ vertices. Since, then the number of edges that can incident from $C_7$ will be $\leq6$ but we have $7$ edges.
This covers all of the cases, and none of these are possible.
$\Longrightarrow$ So, Peterson Graph can not have $C_7$ cycle.

Answer 3

Let $u,v,w$ be three vertices on $C_7$. Then $C_7$ is the union of three edge disjoint paths: a path of length $x$ from $u$ to $v$, a path of length $y$ from $v$ to $w$, and a path of length $z$ from $w$ to $x$. Since $x+y+z=7$ the lengths $x,y,z$ can't all be greater than $2$. Suppose $x\le2$; then the vertices $u$ and $v$ are either adjacent (if $x=1$) or they have a common neighbour (if $x=2$).