2

prove that the graph is connected and has odd length cycle if and only if there exist natural number $r$ that all entries of $A^r$ is positive.

$A$ is adjacency matrix of our graph.

I know if all entries are nonzero then we have connected graph because there is walk of the length of the power and also it is true for converse.

the part that I don't understand is why there should be odd cycle?please help me to figure it out .thanks a lot.

kpax
  • 2,911

1 Answers1

2

If the graph does not have an odd cycle, then it is bipartite, i.e., the vertices can be partitioned into $X$ and $Y$ such there are no edges from $X$ to $X$ or from $Y$ to $Y$. Now start from an edge in $X$. If we can go in $r$ steps to an edge in $Y$, can we go in $r$ steps to an edge in $X$, or vice versa?

Simple examples: consider the graph with two vertices and one edge, or the square graph.

JiK
  • 5,815
  • 19
  • 39