Graph with cycles of odd number

combinatoricsdiscrete mathematicsgraph theory

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

Best 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.

Related Question