Largest Number of Edges

Let $G$ be a graph with maximal number of edges. If $G$ has a face (including the exterior) with more than 3 vertices $V_1 V_2 ... V_n$ , we can connect edge $V_1 V_3$ and get a connected, simple, planar graph with one more edge, contradicting the choice of $G$ . Thus all faces of $G$ have exactly 3 vertices. It is known that the Euler characteristic of planar graphs is 2 if we include the exterior face, thus we have $100-E+F=2$ , so $E-F=98$ . Each face is surrounded by 3 edges, and each edge is surrounded by 2 faces, so $F=\frac {2}{3}E$ . Thus $\frac {1}{3}E=98$ , hence $E=294$ .

It is well known that, in any connected, planar graph with $V$ vertices, $E$ edges, and $F$ faces (ie, regions) including the outer face, $V - E + F = 2$ . One can see this by induction: repeatedly "tearing off" vertices and their associated edges, with a base case of $K_3$ , the triangle.

Each face in a connected, simple planar graph must have at least 3 edges. So $3 F \le 2 E$ . The factor of 2 accounts for the fact that each edge is incident to 2 faces. Combining this with the formula from before, we get $E \le 3 V - 6$ .

This upper bound is attainable. Just start with a triangle, insert a vertex inside it and add edges from that vertex to the triangle's vertices, forming 3 new triangular faces. Repeat this action, at each step using one of the faces produced by the previous step, until we have enough vertices. It's clear that this produces a graph where every face has exactly 3 edges, so we have equality.

Plugging $V = 100$ into $3 V - 6$ gives 294.

We use some lemmas about planar graph as follow:

• Euler formula: if a finite connected planar graph is drawn in the plane without any edge intersections, and v is the number of vertices, e is the number of edges and f is the number of faces then $v - e + f = 2$ .

• In a finite connected simple planar graph, any face (except possibly the outer one) is bounded by at least three edges and every edge touches at most two faces; then these graphs are sparse in the sense that $e ≤ 3v - 6$ if $v ≥ 3$ .

• A simple graph is called maximal planar if it is planar but adding any edge would destroy that properties. All faces (even the outer one) are then bounded by three edges, explaining the alternative term triangular for these graphs. If a triangular graph has $v$ vertices with $v > 2$ , then it has precisely $3v-6$ edges and $2v-4$ faces.

Come back to our problem, we can see that the given graph $G$ have maximal number of edges when it is a maximal planar graph with $3 \cdot 100-6 = 294$ edges.

Assume G has a face touching more than 3 edges, we can then add an edge across the face.

Thus, by 'triangulating' the plane, we obtain the planar graph with the maximal number of edges. All triangulations of a plane has the same number of edges. Starting from v=3, adding a vertex and dividing the outerface maximally creates 2 new faces.

Basically, "If a maximal planar graph has v vertices with v > 2, then it has precisely 3v − 6 edges and 2v − 4 faces.

so,a connected simple planar graph G has as most 294 edges.

For all connected, simple, planar graphs, $e \le 3v-6$ . Then the maximum is attained when equality is at $e=(3)(100)-6=\boxed{294}$

Our goal is to find the maximum number of edges in a graph with 100 vertices that has these properties: 1) Connected: There is a path going from any one vertex to another. 2) Simple: It contains no loops, an edge whose end points coincide, or multiple edges, an edge whose endpoints are identical to anothers. 3) Planar: No edges intersect anywhere but their endpoints.

It may seem daunting to work with 100 vertices, so let's start out small. If we have 1 vertex (V=1), we have 0 edges (E=0), for an edge would violate condition (2). If V=2, we have 1 edge, for any more would violate condition (2). If V=3, we merely add one more vertex to the previous graph with V=2, and draw all the edges that are possible. Doing so results in E=3, and a shape that resembles a triangle. If V=4, we again add another vertex to the previous graph, whether the vertex be "inside" or "outside" of the triangle. We find that either way 3 more edges can be formed, making a total of E=6. If V=5, add another to the previous. If one draws a picture of this situation, one can see that no matter where you put the fifth vertex, it can only connect to three, and not all four, of the previous vertices. Thus we have a total number of E=9. If V=6, again, you may find in a picture that no matter where the new vertex is placed, it can only connect to a maximum of 3 other vertices. Thus E=12.

A pattern seems to be arising. However, to prove that it exists, we have to look more closely at the shapes created when there are more than 2 vertices. With V=3, we got a triangle-like shape. I will define this "TLS" to be a space enclosed on all sides by three edges meeting at only three vertices. Another vertex placed inside the TLS will be able to connect to those three vertices and no others. Thus, three more edges are created, destroying the original TLS, and creating three new TLS's. This can be iterated indefinitely. You may ask, however, what happens when we place a vertex outside of the TLS? Well, if we only have one TLS, the new vertex will be able to connect to all three vertices, and it will indeed create two more TLS's, retaining the prior one, making a total of three. In a conglomerate of TLS's that can be iterated by the previously described processes, exactly three vertices remain "open to the outside." This is fairly obvious in the case of placing a vertex on the inside, and can be easily drawn as true in the case of placing a vertex on the outside of just one TLS. Thus, when one places a vertex outside of a conglomerate of TLS's, 3 new edges are formed and two more TLS's exist.

That proved, for V>2, one can find the explicit formula from the above inductive example to be 3(V-2)=E. Thus, if V=100, E=3(100-2)=294

Also note that using Euler's famous equation F+V=E+2 can also apply, if you consider the plane to be the initial face and that each TLS would separate off their own face. Thus V=2 implies F=1, V=3 implies F=2, V=4 implies F=4, and so on. One can then see that for V>2, F=2(V-2). This would give 2(V-2)+V=E+2, which implies the other formula. This method is probably just as hard, if not harder, to prove.

This would be a maximal planar graph with v=100.

Lemma. All faces of this G are surrounded by 3 edges. Proof by Contradiction. Assume G has a face touching more than 3 edges, we can then add an edge across the face.

Thus, by 'triangulating' the plane, we obtain the planar graph with the maximal number of edges. All triangulations of a plane has the same number of edges. Starting from v=3, adding a vertex inside any face (and connecting it to the three reachable vertices) creates 2 new faces.

If a maximal planar graph has v vertices with v > 2, then it has precisely 3v − 6 edges and 2v − 4 faces.

In short, a connected simple planar graph G has as most 294 edges.

This would be a maximal planar graph with v=100.

Lemma. All faces of this G are surrounded by 3 edges. Proof by Contradiction. Assume G has a face touching more than 3 edges, we can then add an edge across the face.

Thus, by 'triangulating' the plane, we obtain the planar graph with the maximal number of edges. All triangulations of a plane has the same number of edges. Starting from v=3, adding a vertex inside any face (and connecting it to the three reachable vertices) creates 2 new faces.

Basically, "If a maximal planar graph has v vertices with v > 2, then it has precisely 3v − 6 edges and 2v − 4 faces."

All faces of this G are surrounded by 3 edges.

To obtain a planar graph by "triangulation" among vertices:

All triangulations of a plane has the same number of edges. Starting from v=3, adding a vertex inside any face (and connecting it to the three reachable vertices) creates 2 new faces.

If a maximal planar graph has v vertices with v > 2, then it has precisely 3v − 6 edges and 2v − 4 faces. (simple planarity criterion)

For v=100 G has at most 294 edges.

Source : Planar Graph at Wikipedia

For a simple, connected, planar graph with $v$ vertices and $e$ edges, the following simple planarity criteria hold:

If $v ≥ 3$ then $e ≤ 3v - 6$ where $v$ = no. of vertices

Thus, $e_{max}=3v-6$

$\implies e_{max}=300-6$

$\implies e_{max}=294$