4
$\begingroup$
  1. Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$, the number of shortest paths from $A$ to $B$ is odd. Prove that $G$ is a tree.

  2. Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$, the number of paths from $A$ to $B$ is odd. Must $G$ be a tree?

I have tried and found by example that it should be a tree. But could not prove it.

$\endgroup$
2
  • $\begingroup$ No no, triangle is not a bipartite graph..Triangle is an odd cycle having length $3$ $\endgroup$
    – JSN
    Sep 8, 2022 at 18:30
  • $\begingroup$ [removed my stupid comment] $\endgroup$
    – mihaild
    Sep 8, 2022 at 18:31

1 Answer 1

1
$\begingroup$

Here is an idea: It is clear that the graph is connected. Hence, assume by contradiction that there is cycle. Pick the cycle with the least number of edges, and, that among all such cycles, encloses the least surface. Any such cycle has an even number of edges, hence, there are always two pairs of vertices $v_1, v_2, w_1, w_2$ such that, the path $v_1$ to $v_2$ going clockwise on the path is the same length os the path $v_1$ to $v_2$ going anti-clockwise on the path (and the same for $w_1$ and $w_2$. All these paths must have the same length, $\ell$, say. Since the number of shortest paths from $v_1$ to $v_2$ is odd, there must be another shortest path from $v_1$ to $v_2$ and it must be of length exactly $\ell$ (otherwise, there is a shorter cycle). This path cannot go through the interior of the cycle, otherwise, combined with the other part of the original cycle, this gives a new cycle contained in the old one, hence of strictly smaller surface area... So it must go outside and cycle back. But then, such a new path must also exist for $w_1$ and $w_2$, again, it must go outside and circle back. But the new path connecting $v_1$ and $v_2$ "cuts off" this possibility by planarity, hence, it must go through the interior, a contradiction. I do not know how to formally prove this fact, at least with drawings, this is pretty clear... :)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .