A *series-parallel graph* is one of the following:

- \(K_2\), a graph with two vertices and a single edge, such that one vertex is marked the
*source*and the other vertex is marked the*sink*, or - a graph obtained from a
*series composition*of two series-parallel graphs \(G,H\), where the sink of \(G\) is*identified*(glued) to the source of \(H\), where the source of \(G\) is the new source and the sink of \(H\) is the new sink, or - a graph obtained from a
*parallel composition*of two series-parallel graphs \(G,H\), where the two sources are identified, and so are the two sinks, which become the source and the sink of the new graph respectively.

The name comes because they model electric circuits, in particular series and parallel circuits. A series composition is simply putting two smaller circuits in series, and a parallel composition is simply putting two smaller circuits in parallel.

What is the maximum number of edges that a **simple** series-parallel graph with 2015 vertices can have?

×

Problem Loading...

Note Loading...

Set Loading...