ABSTRACT
Despite the fact that many interesting classes of graphs are Cartesian products, almost all graphs are indecomposable. This is easy to show for many cases, such as for trees and complete graphs. For a proof, note that connected graphs have connected factors. If they are nontrivial, every one of them contains an edge. The product of two edges is a square without diagonals; hence, every connected nontrivial Cartesian product contains a square without diagonals. Since trees and complete graphs are connected and contain no squares at all, or at least no squares without diagonals, they are indecomposable, or prime.
