Disclaimer
The Author of this posting offers the information contained within this posting without consideration and with the reader's understanding that there's no implied or expressed suitability or fitness for any purpose. Information provided is for informational purposes only and should not be construed as rendering professional advice of any kind. Usage of this posting's information is solely at reader's own risk.
Liability Disclaimer
In no event shall Author be liable for any damages whatsoever (including, without limitation, damages for loss of use, data or profit) arising out of the use or inability to use the posting's information even if Author has been advised of the possibility of such damage.
Posting
It would be difficult to easily define minimum required bandwidth, because there are multiple variables to consider. I suspect someone has run OSPF and/or EIGRP across 56 Kbps.
During adjacency formation, unsure there's much of an actual minimum (this assuming there's no network control traffic until after adjacency is fully formed). Of course, bandwidth will impact speed of adjacency formation.
After adjacency formation, "correct" (routing) operation not too dependent on bandwidth, per se, except perhaps for speed of convergence. Without QoS, though, lost or delayed Hellos could cause adjacency to drop. Lost or delayed topology information, as I suspect it uses reliable transmission, will likely just further delay network convergence.
PS:
Minimum bandwidth can be an issue for your non- network control traffic. For example, I recall EIGRP has a parameter to limit bandwidth consumption so it doesn't "starve" all other traffic.
