Never Minimal Automata and the rainbow bipartite subgraph problem