Unique graphs

Discrete Mathematics Level pending

Recall that a graph is a collection of vertices where some pairs (may be none or all) are connected by edges. Here we'll only consider labeled undirected simple graphs: no edge connects a vertex to itself, any pair of vertices has at most one edge between them, edges are undirected in the sense an edge from A to B is the same as from B to A, and the vertices are labeled so that the same graph with different labeling is a different graph.

A unique graph is a graph where one cannot label the vertices in some other way to obtain the same graph. In the example above, the first graph is not unique, because after relabeling the vertices to the second graph, the two graphs are identical. However, with an addition of the red edge to produce to the third graph, the resulting graph is unique.

A positive integer \(n \ge 2\) is called boring if there is no unique graph with \(n\) vertices. As the example above shows, \(11\) is not boring due to the existence of the third graph.

You are told that only a finitely many number of positive integers are boring. What is the sum of all boring numbers?


Problem Loading...

Note Loading...

Set Loading...