Wegen fehlender Unterstützung von der Regierung, kann die Brücke nicht gebaut werden.

von der Regierung = Dativ (von wem?)
der Regierung = Genitiv (wessen?)
In der Umgangssprache ist das ok, aber wenn du die Möglichkeit hast, etwas im Genitiv auszudrücken, dann solltest du das auch machen. Zum einen klingt das gebildeter und zum anderen wird das Ersetzen vom Genitiv durch den Dativ von Deutschlehrern immer kritisiert (und von mir auch :D).

Um die zwei Stadtteile (miteinander) zu verbinden, muss die Brücke gebaut werden.

"Verbinden" ist ok, aber klingt ohne "miteinander" komisch, weil dann impliziert werden kann, dass die beiden Stadtteile auch mit etwas anderem verbunden werden können. Also: "miteinander zu verbinden" ist genauer und besser.