I have the answer for c = 1/2.
Just consider the white edges. As you might know, for every (undirected) graph you can can delete at most half of edges to get a bipartite graph. We'll call the partitions A and B. So there are at least half of the white edges between the group A and B. So if we color all the vertices of which ever group to white, there are at least half of the white edges which is connected to at least one white vertex. So we can choose to paint all the vertices of A to white, or all the vertices of B to white. (We'll choose it later)
Now that we partitioned the vertices into two groups, we want to see which partition should we paint to black, the other partition would be colored to white, and as mentioned, for whites the conditions is held.
The black edges between two partitions, will be connected to at least one black vertex whichever way. Now see the black edges inside the partitions. If black edges in partition A is more, we'll color all the vertices of the A to black. And if black edges in partition B is more, we'll do otherwise.
You can see for white and black the conditions is held.
Proof for the theorem used in this solution: Given a graph, partition it into 2 groups whichever way. If there was a vertex in one group, which more than half of its neighbors are in its group, move the vertex to the other partition. You can see this operation will end, and when ended, for each vertex at least half of its neighbors is in the other group. So at least half of the edges is in-between the partitions.
Update: In this proof, by neighbors we mean the number of edges connected to one vertex.
Since you've written $37*36^{72}$, I assume you figured out that it has $73$ vertices. Further, no restriction of any kind is given. So, its more of a problem (and a pretty simple one to be honest) on combinatorics and not graph theory.
Coloring vertices- $73$ vertices, each can choose from $37$ colors $\implies 37^{73}$ ways!
Coloring edges- $73$ vertices $\implies 72$ edges, each can choose from $37$ colors $\implies 37^{72}$ ways!
Best Answer
I misinterpreted the question to mean that the vertices are also colored, so a vertex cannot be incident to two connected red edges while also being incident to two connected black edges. The correct interpretation is that only the interior of the edges is colored - the vertices are uncolored (or perhaps multicolored is a good way to think of it). So a set $S$ of red points is connected if $S$ is in the same connected component of the tree when you delete the black part.
Fortunately we can reduce the original problem to the problem I was thinking of. Color each non-root vertex according to the nearest color used on the edge leading to the root vertex, and color the root arbitrarily. Each connected component is split into at most three components by this process. So if the original tree had $n'$ connected components, the new tree has at most $n=3n'$ connected components. Use this $n$ in the following argument.
Yes, we can use any $h$ with $3^h>2(n+1)3^n.$
Let $R_1,\dots,R_r$ be the connected components of the red part, and $B_1,\dots,B_b$ the connected components of the blue part. For any set $S$ let $S^*$ denote the set of all points $p$ such that the shortest path from $p$ to the root of the tree goes through $S.$ (Sort of like taking all descendents, but including points in edges as well.) If the root of the tree is red, then the total length of the red part is $$L(R_1\cup\dots\cup R_r)=L(R^*_1)+\dots+L(R^*_r)-L(B^*_1)-\dots-L(B^*_b)$$ where $L$ means total length. This is a form of the exclusion-inclusion formula.
For any connected set $S$ there is a unique point $p$ in the closure of $S$ nearest to the root. The distance of $p$ to a leaf can be written as $d_0+D$ where $D$ is an integer and $d_0\in[0,1)$ if $p\in S,$ and $d_0\in(0,1]$ if $p\not\in S.$ Then
$$L(S^*)=d_0+3+3^2+\dots+3^D=d_0+\tfrac32(3^D-1).$$
For example if $S^*$ consists of a vertex, three child leaves and the edges in between, then $D=1$ and $L(S^*)=3.$
The total length of the tree is $\tfrac32(3^h-1).$ So it suffices to show that a sum of $n$ numbers of the form $\pm (d_0+\tfrac 32(3^D-1))$ cannot equal $\tfrac34(3^h-1).$ Dividing through by $\tfrac32 3^h,$ we want to show that a sum of $n$ numbers of the form $\pm 3^{D-h}$ cannot equal $\tfrac 12$ to within additive error $3^{-h}(n+1).$ Using $3^h>2(n+1)3^n$ this follows from:
Using the rules $3^x+3^x=3^{x+1}-3^x$ we can reduce to the case where the $x_i$ are distinct - a balanced ternary representation. Wlog $x_1$ is the largest. The sum $3^{x_1}\pm\dots\pm 3^{x_n}$ lies in the range $(\tfrac12 3^{x_1},\tfrac 32 3^{x_1}),$ which means we're done unless $x_1\in\{0,-1\}$ - we don't need to consider cases where $3^{x_1}\pm\dots\pm 3^{x_n}$ is less than $\tfrac16$ or greater than $\tfrac32.$ The case $n=1$ is just arithmetic: $|1-\tfrac12|,|\tfrac13-\tfrac12|\geq \tfrac16.$ For $n>1$ we can use induction; the quantity $t=\pm 3^{x_2}\dots\pm 3^{x_n}$ satisfies $|-t-\tfrac 12|,|t-\tfrac 12|\geq \tfrac12 3^{-(n-1)}.$ For $x_1=0$ use $$|1+t-\tfrac12|=|t+\tfrac12|=|-t-\tfrac12|\geq\tfrac12 3^{-(n-1)}\geq\tfrac12 3^{-n}.$$ For $x_1=-1$ use $$|\tfrac13+t-\tfrac12|=\tfrac13|3t-\tfrac12|\geq \tfrac12 3^{-n}.$$