2
$\begingroup$

let $G(V,E)$ be a biconnected symmetric graph without self-loops or parallel edges and, let $G$ contain a cycle of odd length, i.e. $G$ is not bipartite.

Questions:

  • what is known about upper bounds on the number of $v\in V$ that are not on any odd cycle
  • what is known about upper bounds on the number of edges $e\in E$ that are not adjacent to any vertex of an odd cycles
  • what are small examples of biconnected and non-bipartite graphs that have vertices not on any odd cycle or edges that are adjacent to two such vertices
Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

In biconnected non bipartite graph, every vertex $v$ belongs to an odd cycle. Indeed, assuming the contrary take the shortest path $vu_1\dots u_m$ from $v$ to an odd cycle $C\ni u_m$. Since $G-u_m$ is connected, there exists a path between $vu_1\dots u_{m-1}$ and $C-u_m$. Consider the shortest such path $P$, let it start at $u_j$ and end at $w\in C$, $w\ne u_m$. Then $P, u_j\dots u_m$ and one of two arcs of $C$ between $u_m$ and $w$ form an odd cycle and the path $vu_1\dots u_j$ from $v$ to this cycle is shorter than $vu_1\dots u_m$. A contradiction.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.