Problem statement: show there exist positive constants $c_1$ and $c_2$ such that for any $n\geq 3$, whenever $T_1$ and $T_2$ are two trees on the set of vertices $X = \{1, 2, ..., n\}$, there exists a function $f : X \to \{-1, +1\}$ for which $$\bigg | \sum_ {x \in P} f (x) \bigg | <c_1 \log n$$ for any path P that is a subgraph of $T_1$ or $T_2$ , but with an upper bound $c_2 \log n / \log \log n$ the statement is no longer true.
My approach
I’m trying to give the Counterexample
Let $n = 2^k$, where $k$ is a positive integer. We define the following:
$T_1$ is a path graph on $n$ vertices. $T_2$ is a star graph with a center vertex $r$ and $n-1$ leaves.
$f(r) = 1 \text{ and } f(x) = -1 \text{ for all other vertices } x \in X.$
Lower bound for paths in $T_1$: Any path $P$ in $T_1$ will have all vertices assigned $f(x) = -1$ except possibly the endpoints. Therefore, $ | \sum_{x \in P} f(x) | = 2$