Talk:Series–parallel graph

A fact from Series–parallel graph appeared on Wikipedia's Main Page in the Did you know column on 11 March 2007. The text of the entry was as follows:

Did you know... that a series-parallel graph is a mathematical model of series and parallel electric circuits with two different nodes called source and sink, indicating the direction of the electrical current flow?

A record of the entry may be seen at Wikipedia:Recent additions/2007/March.

Wikipedia

Mathematics C‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
C	This article has been rated as C-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Removed: apparently false characterization of series-parallel graphs

The Properties section of the article contains a paragraph that previously read as follows:

Every series-parallel graph has treewidth at most 2 and branchwidth at most 2. Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every biconnected component is a series-parallel graph.^[1]^[2] The maximal series-parallel graphs, graphs to which no additional edges can be added without destroying their series-parallel structure, are exactly the 2-trees. Graphs of treewidth at most 2 have an explicit forbidden minor characterization, implying that a graph is series-parallel if and only if its biconnected components are linked in a path and it excludes the complete graph K₄ as a minor.

But the last sentence, claiming that a graph is series-parallel if and only if its biconnected components are linked in a path and it excludes the complete graph K₄ as a minor, is false, as the Wheatstone bridge graph shows:

This graph is connected, its biconnected components are linked in a path, and it does not contain K₄ as a minor, but it is not a series-parallel graph.

Therefore, I have removed the last sentence of this paragraph. —Bkell (talk) 18:09, 28 May 2013 (UTC)[reply]

^ Bodlaender, H. (1998). "A partial k-arboretum of graphs with bounded treewidth". Theoretical Computer Science. 209 (1–2): 1–45. doi:10.1016/S0304-3975(97)00228-4.
^ Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "On matroids of branch-width three". Journal of Combinatorial Theory, Series B. 86 (1): 148–171. doi:10.1006/jctb.2002.2120.

[1] Bodlaender, H. (1998). "A partial k-arboretum of graphs with bounded treewidth". Theoretical Computer Science. 209 (1–2): 1–45. doi:10.1016/S0304-3975(97)00228-4.

[2] Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "On matroids of branch-width three". Journal of Combinatorial Theory, Series B. 86 (1): 148–171. doi:10.1006/jctb.2002.2120.

[1]

[2]