Unique graphs

Probability 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 2 n \ge 2 is called boring if there is no unique graph with n n vertices. As the example above shows, 11 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?


The answer is 14.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

0 solutions

No explanations have been posted yet. Check back later!

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...