ABSTRACT
The Sabidussi-Vizing Theorem 6.6 states that connected graphs factor uniquely into primes with respect to the Cartesian product. The proof is surprisingly short. The first aim of this chapter is to provide an almost equally short argument that the prime factors of a connected graph on n vertices and m edges can be computed in O(mn) time.
