Planar graphs and greatest common subgraphs (Q687720): Difference between revisions

A greatest common subgraph of two graphs \(G_ 1\) and \(G_ 2\) of equal size is defined as any graph of maximum size without isolated vertices that is isomorphic to a subgraph of both \(G_ 1\) and \(G_ 2\). The set of all greatest common subgraphs of \(G_ 1\) and \(G_ 2\) is denoted by \(\text{gcs} (G_ 1,G_ 2)\). If \(| \text{gcs} (G_ 1,G_ 2)|=1\), then \(G_ 1\) and \(G_ 2\) are said to have a unique greatest common subgraph. The author shows that with the exception of eight connected planar graphs every connected planar graph is the unique greatest common subgraph of two nonisomorphic connected planar graphs of equal size.