Haskell, 106 bytes

Port of my BQN answer, takes the number of vertices on the left.

import Data.List n!([u,v]:e)=zipWith(-)(n!e)$0:(n-1)!nub[sort$take 2$(r++[v])\\[u]|r<-e] n!_=1:(0<$[1..n]) 

Try it online!

I feel like there should be a shorter way to replace \$u\$ with \$v\$ in a list (currently take 2$(r++[v])\\[u]).