2
$\begingroup$

Here is the solution which I am not getting, I am writing it in points along with the doubts I have (written in bold)-:

$1$ 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.

$2$.Thus there are seven edges from $V \left(C\right) $ to the remaining three vertices.

$3$ 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.

$4$.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

In short I am not getting major of it .. I know it is duplicate of here please help me out !

$\endgroup$
1
$\begingroup$

For point $1$, Imagine the (hypothetical) $7-$cycle $C$ as a heptagon. The proposed "additional edge" is a diagonal of this heptagon. The statement is equivalent to saying that any such diagonal cuts the heptagon in to two pieces, one of which is a triangle or quadrilateral. Because the Petersen graph has no cycles of length $\lt5$, it means that the vertices in such a $C$ cannot be connected to each other except by the edges that are part of $C$.

Point $2$ follows directly from this and the fact that every vertex of the Petersen graph has degree $3$: since they each vertex in $C$ has $2$ edges in $C$, they must each have one that is not, and by point $1$, this edge must connect to a vertex not in $C$.

Point $3$ says that there is no way to connect the other ends of the $7$ edges mentioned in point $2$ to the three vertices not in $C$. This is because, after you've connected $2$ to each of them, you still have one left, which will be the third edge connected to whatever vertex you connect it to.

Point $4$ has two parts. The first says that given $3$ vertices $C$ of $C$, at least $2$ of them are connected by a path of length $\le2$ in $C$. This is because if one of them is $3$ edges away from both of the others, then the others are neighbors because $C$ is a cycle of length $7$. The second half simply says that, since point $3$ tells us that there is a vertex (call it $a$) not in $C$ connected to $3$ vertices in $C$, and (by the first part of $4$) $2$ of these are connected by a path of length $2$ in $C$, the edges connecting $a$ to those $2$ vertices along with the path connecting them in $C$ is a cycle of length $4$. $\square$

$\endgroup$
2
$\begingroup$

The Petersen graph is isomorphic to the Kneser graph $\text{KG}(5,2)$, hence we may assume that every vertex of the Petersen graph is labelled with a $2$-subset of $\{1,2,3,4,5\}$, and two vertices are joined by an edge if the corresponding subsets are disjoint. For instance,

$$\ldots\to(1,2)\to(4,5)\to(1,3)\to(2,5)\to(1,4)\to(2,3)\to(1,5)\to(3,4)\to\ldots $$ is a cycle with length $8$. Assume there is some cycle with length $7$. Without loss of generality (the Petersen graph is vertex-transitive) we may assume it is given by: $$\ldots\to(1,2)\to(?,?)\to(?,?)\to(?,?)\to(?,?)\to(?,?)\to(4,5)\to\ldots $$ Since $5<2\cdot 3$, the Petersen graph is triangle-free. Additionally, it is not difficult to prove there is no cycle with length $4$. Let $u,v,w$ the vertices not included in the previous cycle. Among $\{u,v,w\}$ there are at most two edges, but the neighbourhood of every vertex has cardinality $3$, so there are at least $7$ edges between $\{u,v,w\}$ and the vertices in the cycle. The pigeonhole principle then implies that there is a cycle with length $3$ or $4$, contradiction.


I will provide you a "spectral" alternative, too. Let $P$ be the adjacency matrix of $\text{KG}(5,2)$.
The diagonal elements of $P^m$ count the number of paths that starts at some vertex and return there in $m$ steps. We know in advance that the diagonal elements of $P^2$ equal three, the diagonal elements of $P,P^3$ equal zero and the diagonal elements of $P^4$ equal $15$. If we count the number of paths that start at some vertex and return there in $5$ steps ($12$), then compute $P^7$, we may easily check that there are no cycles with length $7$ in $\text{KG}(5,2)$.

$\endgroup$
  • $\begingroup$ @ jack i am not getting "petersen graph is vertex -transitive" we may assume it is given by : ....!!! please explain $\endgroup$ – virat Nov 2 '16 at 20:39
  • $\begingroup$ @sourav: since the Petersen graph is vertex-transitive (it is isomorphic to a Kneser graph, and every Kneser graph is trivially vertex-transitive), we may assume that the "first" and "last" element of the $7$-cycle are labelled with $(1,2)$ and $(4,5)$. $\endgroup$ – Jack D'Aurizio Nov 2 '16 at 20:50
  • $\begingroup$ ,total number of vertex possible =$\binom{5}{2}=10$ ,so $7$ length cycle will not contain 3vertices ,let it be $u$ , $v$, $w$....do you mean this? $\endgroup$ – virat Nov 2 '16 at 20:54
  • $\begingroup$ That is true, but I meant what I wrote, i.e. that we may assume without loss of generality that two neighbouring vertices of the $7$-cycle are labelled with $(1,2)$ and $(4,5)$. $\endgroup$ – Jack D'Aurizio Nov 2 '16 at 20:55
  • 1
    $\begingroup$ @sourav: seven edges to seven vertices mean that every element of the (supposed) $7$-cycle is connected to $\{u,v,w\}$, or that $2$ elements of $\{u,v,w\}$ are connected to the same element in the $7$-cycle. $\endgroup$ – Jack D'Aurizio Nov 3 '16 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.