External Page
Proving that the answer is
can be done by induction on the number of vertices.
An uncommon feature of the proof is that the
base of the induction consists of two values of
:
and
.
The corresponding graphs are the complete
-bipartite
graph and the complete
-bipartite
graph:

Figure 12:
For both of the above graphs any path of length 2 is an induced subgraph (the first doesn't even have such paths). Under this condition, the graphs have the maximum number of edges among all such graphs with


Now, assume that our answer holds true for all graphs with up to
vertices, and let
be a graph with
vertices
which has no triangles. Since
must have
at least one edge, select an arbitrary edge
and remove from the graph both
vertices
and
together with the edges incident to them.
The resulting graph
has no triangles; it has
vertices;
thus, inductively, the number of edges in
is at most
.
Now we count the number of edges removed from when
and
are removed.
Since
has no triangles, for every vertex in
other than
and
,
at most one edge adjacent to
or
is removed.
Therefore, the number of edges removed is bounded by

Equation 2
where one counts the removal of edge
.

Figure 13:
the vertices adjacent to b are not adjacent to a the vertices adjacent to a are not adjacent to b
We are now in a position to estimate the total number of edges in :

Equation 3
simplifying, we get

Equation 4
... and simplifying this further, we conclude the proof:

Equation 5