Problem 677
Coloured Graphs
Let $g(n)$ be the number of undirected graphs with $n$ nodes satisfying the following properties:
- The graph is connected and has no cycles or multiple edges.
- Each node is either red, blue, or yellow.
- A red node may have no more than $4$ edges connected to it.
- A blue or yellow node may have no more than $3$ edges connected to it.
- An edge may not directly connect a yellow node to a yellow node.
For example, $g(2)=5$, $g(3)=15$, and $g(4) = 57$.
You are also given that $g(10) = 710249$ and $g(100) \equiv 919747298 \pmod{1\ 000\ 000\ 007}$.
Find $g(10\ 000) \bmod 1\ 000\ 000\ 007$.
图染色
记$g(n)$为有$n$个结点并满足以下性质的无向图总数：
- 该图是连通图、无环、无重边。
- 每个结点被染上红色、蓝色或黄色之一。
- 每个红色结点至多与$4$条边相连。
- 每个蓝色或黄色结点至多与$3$条边相连。
- 黄色结点之间不能直接相连。
例如，$g(2)=5$，$g(3)=15$，$g(4) = 57$。
还已知$g(10) = 710249$，$g(100) \equiv 919747298 \pmod{1\ 000\ 000\ 007}$。
求$g(10\ 000) \bmod 1\ 000\ 000\ 007$。