Abstract: | Define a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs Kn' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle-free graphs. |