Series-parallel graphDiscrete Mathematics Level 5
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?