Largest Number of Edges

Probability Level 5

Suppose GG is a connected, simple, planar graph with 100100 vertices. What is the largest possible number of edges in GG?

Details and assumptions

A graph is connected if there is a path from any one vertex to any other.
A graph is simple if it contains no loops and no multiple edges.
A loop is an edge whose endpoints coincide.
A multiple edge is an edge whose endpoints are identical to the endpoints of another edge.
A graph is planar if it can be drawn so that no two edges intersect at points other than their endpoints. The edges need not be straight line segments, and can be curved lines.


Problem Loading...

Note Loading...

Set Loading...