　一般に $N=12 \left( \gt 4 \right)$ とする.
島を頂点 $1, 2, \ldots, N$, 橋を辺とすることでOMC国を無向グラフとみなす.\
　このとき, 問題文中の条件は以下のように言い換えられる.

- どの色についても, その色以外で塗られた辺を全て取り除いた後のグラフは連結でない.
- どの頂点についても, $1$ 本以上の赤色で塗られた辺の端点となっている. 

これらの条件のもとで, 赤色以外で塗られた辺の数 $m$ が最小値をとるようなものを考えることにする.\
　赤色で塗られた辺のみを残したとき, 各連結成分に含まれるような頂点集合を 
$V_1, V_2, \ldots, V_k$ とおく. ここで
$$
|V_1| \leq |V_2| \leq \cdots \leq |V_k|
$$
とする. 条件より $k \geq 2$ および $ 2 \leq |V_1| \leq \dfrac{N}{2}$ である. 
このとき, 辺数を考えれば

$$
|V_1|\sum_{i=2}^{k}|V_i| + |V_2|\sum_{i=3}^{k}|V_i| + \cdots + |V_{k-1}|\sum_{i=k}^{k}|V_i| \leq m
$$

が成立する. なお, 等号は各連結成分に赤色以外の辺が含まれない場合に成立する.\
　ここで, $N=|V_1|+\cdots+|V_k|$ に注意すれば, 左辺は以下のように表現できる.
$$
\dfrac{1}{2}\left( N^2-|V_1|^2-\cdots-|V_k|^2 \right)
$$
したがって, いま $|V_1|^2+\cdots+|V_k|^2$ の最大化を考える. ここで
$$
\big(|V_{k-1}|+|V_k|\big)^2\gt |V_{k-1}|^2+|V_k|^2
$$
であることから $k=2$ の場合のみを考えればよく, このとき $|V_1|=2$ とするのが一意に最善である.\
　すなわち $m\geq 2N-4$ と評価できる. 等号が成り立つとすれば, ある頂点 $v_1\lt v_2$ が存在し, これらとこれら以外の頂点を結ぶ辺はすべて赤色でなく, それ以外の辺はすべて赤色である.\
　いま $v_1,v_2$ を固定して考える. 以上で与えた条件のみでは $2^{2N-4}$ 通りであるが, このうち条件をみたさないものを除外する. ここで, $v_1, v_2$ と異なる頂点 $v$ であって, 
$v$ と $v_1$, $v$ と $v_2$ を結ぶ辺が共に緑色で塗られているものが存在するならば, 
そのうち一つを選び $v_g$ とする. 
青色についても同様に, 存在するならばそのうち一つを $v_b$ とする.

- $v_g$,  $v_b$ がともに存在しないとき, 
青色, 緑色それぞれの色の辺について $v_1, v_2$ が連結でないため, 適する.
- $v_g$,  $v_b$ の一方のみが存在するとき, 
その色を $C$ とすると, $v_1, v_2$ は色 $C$ の辺によって連結であり, 
$v_1, v_2$ と異なる任意の頂点 $v$ について, 
$v$ は $v_1, v_2$ の少なくともいずれか一方と色 $C$ によって連結であるため, 不適である. 
- $v_g$,  $v_b$ がともに存在するとき, 
青色, 緑色それぞれの色の辺について $v_g, v_b$ が連結でないため, 適する.

　よって, 上で定めたような $v_g$,  $v_b$ の一方のみが存在する場合を除けばよい.
$v_1, v_2$ と異なる $N - 2$ 個の頂点 $v$ について接続する $2$ 個の辺の色を考えることで,
これは $2 \left( 3^{N-2} - 2^{N-2}\right)$ 通りであることがわかる. \
　以上より, 全体で求めるべき塗り分け方は
$$\dbinom{N}{2} \left( 2^{2N-4} - 2 \left( 3^{N-2} - 2^{N-2}\right) \right)$$
通りである. 解答すべき値は特に $N = 12$ の場合で与えられて, 
$\mathbf{61546716}$ 通りである.
公式解説
https://onlinemathcontest.com/contests/omc152/editorial/3921
　OMC国は $12$ 個の島からなり，どの相異なる $2$ 個の島についても，ちょうど一本の橋で双方向に結ばれています．おもち君はこれらの橋を，以下の条件をみたすように赤色・緑色・青色のいずれかで塗り分けることにしました：

- どの色 $C$ に対しても，相異なる $2$ 個の島 $I_1,I_2$ が存在し，$C$ で塗られた橋のみを渡ることを繰り返して $I_1$ から $I_2$ に到達できない．

- どの島に対しても，ある他の島が存在し，それらは赤色で塗られた橋で結ばれている．

このような塗り分け方のうち，赤色で塗られた橋の本数が最大値をとるようなものがいくつあるかを求めてください．ただし，すべての島は区別して考えるものとします．