8
$\begingroup$

Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) triangular faces having clockwise orientation. Prove that the number of oriented rooted spanning trees, say oriented from the root $v_0$, is an odd number. (An oriented spanning tree rooted at $v$ is an acyclic subgraph in which every vertex other than $v$ has indegree $1$.)

In attached example:

I counted $11$ trees, and my strategy was to put the trees in pairs, such that one tree is paired with itself, but it gets complicated like in the example when we have two edges from $v_1$ to $v_2$. Also because we have an odd number of vertices maybe it will be simpler to establish the parity of all oriented-trees.

Edit: Later form the matrix method I computed the matrix for this example:

$\left( \begin{array}{ccccc} 1 & -1 & 0 & 0 & 0 \\ 0 & 4 & -2 & -1 & -1 \\ -1 & -1 & 3 & -1 & 0 \\ 0 & -1 & 0 & 2 & -1 \\ 0 & -1 & -1 & 0 & 2 \\ \end{array} \right)$

And the number of all oriented spanninng trees is the product of non-zero eigenvalues so here it gives $55$, so rooted spanning is $11$ as expected.

But I still dont see how the condition of triangular faces translates to the matrix or its eigenvalues.

EDIT2:

A strategy by induction will make sense if the folowing is true:

If we delete all triangles with vertices $v_j$ of valecy $2$ like in the picture below (top row), then there is a situation like in the picture below (bottom row) where we have a vertex $v_j$ of valency $4$ adjacent to a face of $2$ sides (a bigon).

enter image description here

Does anyone know if the above statement is always true?

Improve this question
$\endgroup$
7
  • $\begingroup$ Are there straightforward upper and/or lower bounds for the number you are looking for? $\endgroup$
    – Sam Sanders
    Commented Mar 12, 2021 at 12:27
  • 1
    $\begingroup$ This was also posted on MSE math.stackexchange.com/questions/4048506/… $\endgroup$
    – Hugo Manet
    Commented Mar 12, 2021 at 12:34
  • 2
    $\begingroup$ This seems like an interesting question to me. There are many things to try: BEST theorem, oriented Matrix-Tree theorem, oriented planar duality, a simple induction peeling off outer vertices. But I don't see a simple solution. And I assume the OP has a reasonable amount of computational evidence for the claim? $\endgroup$
    – Sam Hopkins
    Commented Mar 13, 2021 at 4:40
  • $\begingroup$ I have some computational evidence, and I am not interested in the bounds in this problem. $\endgroup$
    – user174224
    Commented Mar 14, 2021 at 11:36
  • $\begingroup$ That's intriguing. Why do you ask to prove, not "prove or disprove"? Are you sure that this must be true? $\endgroup$
    – Fedor Petrov
    Commented Mar 19, 2021 at 21:58

0

Reset to default

You must log in to answer this question.