Graph with cycles of odd number

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 Answer

Hints:

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.

• 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)? – ChonChon Mar 25 at 21:02
• @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$ – Arthur Mar 25 at 22:44