Counting number of special subset of vertices in a tree

Question

As defined in this article, an ordered pair $ (X,Y) $ of disjoint subsets of the vertices of a graph $ G $ with $ \vert X \vert = \vert Y \vert =2 $, is called an odd pair if the number of edges with one endpoint in $ X $ and another in $ Y $ is odd. Denote the number of odd pairs in $ G $ by $ s(G) $ (Note that if $ X \neq Y$, then $(X, Y) \neq (Y, X)$).

If $ G $ is the star graph $ S_{n} $, it is easily seen that $s(G) = 0$.

If $ G $ is the graph of order $n$ with the sequence of degrees $ \lbrace n-2, 2, 1, 1, \ldots ,1 \rbrace $, I have proved that $s(G) = 4(n-3)^{2}$. (Here, $G$ is very similar to star graph.)

Now, I guess that for every tree $T$ of order $n$ such that $T$ is not star graph, $s(T) \geq 4(n-3)^{2}$. I have tested this by computer search, but I couldn't prove that. Can anyone help? I think using induction can lead to the proof.

Thanks in advance.

Answer 1

Let us prove the desired bound $2(n-3)^2$ for the number of unordered odd pairs by induction on $n$, base case being $n=4$.

Suppose that $n\geq 5$. Take a leaf $a$ with a unique neighbour $b$; let $\deg b=k+1\leq n-2$. We assume that $a$ is chosen so as to maximize $k$. In particular, this ensures that $G-a$ is not a star, so it contains at least $2(n-4)^2$ odd pairs. Moreover, if $k=n-3$, we get the extremal graph which has been already investigated. So we assume $k\leq n-4$.

Now it suffices to find $2(n-3)^2-2(n-4)^2=2(2n-7)$ additional odd pairs containing $a$. These are almost provided by the following collections.

$(1)$ Pairs of the form $(\{a.b\},\{c,x\})$ where $c\in N(b)$ and $x\notin \{a,b\}\cup N(b)$. There are $k(n-2-k)$ such pairs.

$(2)$ Let $xy$ be an edge in $G-\{a,b\}$ (there are $n-k-2$ such). Any vertex $d\notin\{a,b,x,y\}$ is not adjacent to one of $x$ and $y$ --- say to $x$. Then $(\{a,x\},\{d,y\})$ is a desired odd pair; there are at least $(n-4)(n-k-2)$ such pairs.

$(3)$ Pairs of the form $(\{a,c\},\{b,d\}$, where $abcd$ is a path of length 3 --- there is at least one such.

All in all, this provides $$ (n-k-2)(k+n-4)+1=(n-3)^2-(k-1)^2+1\geq (n-3)^2-(n-5)^2+1=2(2n-7)-1 $$ additional odd pairs. We need thus to find one extra additional pair in the case $k=n-4$ (otherwise the above inequality is strict).

If $n\geq 6$ (so $k\geq 2$), then the estimate in $(2)$ is not sharp: for any edge $xy$ in $G-\{a,b\}$ there exists a neighbor $c\neq a$ of $b$ which is adjacent to neither $x$ nor $y$, so both pairs $(\{a,x\},\{c,y\})$ and $(\{a,y\},\{c,x\})$ work. This already increases the bound by $2$.

If $n=5$, then $k=1$ only when $G$ is a path. In this case we find $8$ odd pairs by hands.