Having an exercise from an old book of graph theory that does not contain the solution. My graph theory skills are at best entry-level. Need the concept of this problem to be explained(if possible) not the solution.

Having a simple non-directed graph that contains cycles of odd length but no $3$-length cycle. If $C$ a minimal cycle of odd (no 3) length of the graph then show:

1)if $x∈V(G) - V(C)$ and $u,w∈V(C)$, with $u,w$ being adjacent to $x$, the vertices $u,w$ are connected by a path length 2 that are made from edges of cycle c.

2)every vertex of $G$ which doen't belong to $V(C)$ have at most 2 neighborhoods in $V(C)$.



1) Clearly $u, w$ are connected in the cycle. It's a cycle, after all. Let's say they aren't connected by a length-2 path in $C$. Then the shortest path between them in $C$ is either of length $1$ or of length more than $2$. Show that either of these cases leads to some contradiction.

2) Take an $x\notin V(C)$ with $3$ distinct neighbours $u, v, w\in V(C)$. Use the result of 1) to discuss what $C$ must look like and again reach a contradiction.

  • $\begingroup$ Your answer is very helpful at least for the 1st, and i am thinking i am close at solving it, so the maximum favorable distance between u,w can be n-1/2 (n=vertices), the connection between x,u,w creates a cycle which if odd is smaller than the C which can't be done (since C is the smallest one), but what if length is 6 and the distance of path between u,w is 3(or more)? $\endgroup$ – ChonChon Mar 25 at 21:02
  • $\begingroup$ @ChonChon If the shortest path from $u$ to $w$ in $C$ has length $1$, then what can you say about $xuwx$? If the shortest path in $C$ from $u$ to $w$ is 3 or longer, then one of the two paths from $u$ to $w$ in $C$ has even length ($C$ has odd length and the length of $C$ is the sun of the lengths of the two paths). Can you use $C$ and $uxw$ to make an odd cycle shorter than $C$? Finally, for 2), by 1), there must be a path in $C$ of length 2 from $u$ to $v$, and such a path from $v$ to $w$, and such a path from $w$ to $u$. These three paths together make a cycle of length $6$ contained in $C$ $\endgroup$ – Arthur Mar 25 at 22:44

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.