完全2部グラフformula_1や、対称グラフ(例えば立方体の頂点と辺から成るようなグラフ)は、どのようなものであっても辺推移グラフである。