Series-parallel graph

Suppose that the maximum number of edges of a simple series-parallel graph is $M(n)$ . We claim that for $n \ge 2$ , $M(n) = 2n-3$ .

This is trivially true for $n = 2, 3$ . The complete graph on $2, 3$ vertices has $1, 3$ edges respectively, and they are series-parallel graphs (after assigning the source/sink). ( $K_2$ is trivial. $K_3$ is obtained by composing two $K_2$ 's in series to form $K_{1,2}$ , a path of two edges, then composing that with a $K_2$ in parallel.)

Suppose the claim is true for all $n \le N$ , and we want to show that the claim is also true for $n = N+1$ .

We will first prove a simple claim: if a simple series-parallel graph has the maximum number of edges for its number of vertices, then the source and the sink are connected by an edge. This is simple: if it isn't, then it can be composed with $K_2$ in parallel to give said edge, contradicting maximality.

Now that we have proved the claim, let $G$ be a simple series-parallel graph of $n = N+1$ vertices. Also, assume that the source and the sink of $G$ are not connected by an edge. By the claim above, this implies that $|E(G)| \le M(n) - 1$ ; $G$ has at most $M(n) - 1$ edges. Also, one of the following is true:

Case 1: $G$ is formed from two simple series-parallel graphs $G', H'$ by composing them in series.

Let $a = |V(G')|, b = |V(H')|$ . Then $n = a+b-1$ ; all vertices of $G', H'$ are present, but a pair of them are glued together into one, so we're missing one vertex. Additionally, since they are series-parallel graphs, we know that $a, b \ge 2$ , which implies $a, b \le n-1$ , and so we can apply induction to show that $G', H'$ has at most $2a-3, 2b-3$ edges respectively. Thus $G$ has at most $(2a-3)+(2b-3) = 2(a+b-1)-4 = (2n-3) - 1$ edges. Taking across all $G$ , we thus have $\max (|E(G)|-1) = M(n)-1 \le (2n-3)-1$ , or $M(n) = 2n-3$ .

Case 2: $G$ is formed from two simple series-parallel graphs $G', H'$ by composing them in parallel.

Let $a = |V(G')|, b = |V(H')|$ . Then $n = a+b-2$ ; all vertices of $G', H'$ are present, but two pairs are glued together respectively, so we're missing two vertices. Additionally, since they are series-parallel graphs, we know that $a, b \ge 2$ . In fact, if $a = 2$ , then $G' = K_2$ , but this would mean the source and the sink of $G$ are connected by an edge (the edge of $G'$ ), contradiction. Likewise with $b = 2$ . Thus $a, b \ge 3$ , which implies $a, b \le n-1$ .

We can apply induction to show that $G'$ has at most $2a-3$ edges. But we can do better: we know that if $G'$ has $2a-3$ edges, then there is an edge between the source and the sink of $G'$ . But the source and the sink of $G$ are the same as that of $G'$ , so this would make an edge between the source and the sink of $G$ , contradiction. So $G'$ has at most $2a-4$ edges. Likewise, $H'$ has at most $2b-4$ edges. Thus $G$ has at most $(2a-4)+(2b-4) = 2(a+b-2)-4 = (2n-3) - 1$ edges. Taking across all $G$ , we thus have $\max (|E(G)|-1) = M(n)-1 \le (2n-3)-1$ , or $M(n) = 2n-3$ .

In both cases, we have shown that $M(n) = 2n-3$ , proving the claim. Thus $M(2015) = \boxed{4027}$ .