diff --git a/routing/router.go b/routing/router.go
index <HASH>..<HASH> 100644
--- a/routing/router.go
+++ b/routing/router.go
@@ -727,6 +727,13 @@ func (r *ChannelRouter) pruneZombieChans() error {
 		}
 	}
 
+	// With the channels pruned, we'll also attempt to prune any nodes that
+	// were a part of them.
+	err = r.cfg.Graph.PruneGraphNodes()
+	if err != nil && err != channeldb.ErrGraphNodesNotFound {
+		return fmt.Errorf("unable to prune graph nodes: %v", err)
+	}
+
 	return nil
 }
routing: prune graph nodes after pruning zombie channels

We do this to ensure we don't leave any stray nodes in our graph that
were part of the zombie channels that we've pruned.