Geodetic graph

Geodetic graphs were introduced in 1962 by Øystein Ore, who observed that they generalize a property of trees (in which there exists a unique path between each two vertices regardless of distance), and asked for a characterization of them.

[1] Although these graphs can be recognized in polynomial time, "more than sixty years later a full characterization is still elusive".

by a path of the same odd length will produce another geodetic graph.

[5] In the case of a complete graph, a more general pattern of replacement by paths is possible: choose a non-negative integer

[3] Similarly, because a cycle graph is geodetic when it has odd length, every cactus graph in which the cycles have odd length is also geodetic.

[4] Geodetic graphs may be recognized in polynomial time, by using a variation of breadth first search that can detect multiple shortest paths, starting from each vertex of the graph.

[3] In particular, as a subset of diamond-free graphs, the geodetic graphs have the property that every edge belongs to a unique maximal clique; in this context, the maximal cliques have also been called lines.

For the binary affine plane with four points and six two-point lines in three parallel pairs, the result of this construction is the Petersen graph, but for higher-order finite affine planes it produces graphs with two different degrees.