Talk:Minor (graph theory)

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	High Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. A diagram showing the process of edge conraction that leads from eth first graph to the second would be useful. General expansion needed, especially applications. Tompw (talk) 15:30, 4 January 2007 (UTC)

Flamholz's definition works. But it *should* refer to Wagner's theorem. Kuratowski's theorem is similar (and equivalent) but has a different statement. --75.3.130.58 23:57, 5 August 2006 (UTC)

Shouldn't edge deletion be included in the definition of minor?
Peter Kwok 20:22, 2004 Jun 22 (UTC)

I was pretty confused by this omission. The example doesn't make any sense unless you delete edges instead of contracting them. But I'm not an expert ... jrn 15:00, 2005 Apr 5 (UTC)

I agree. Can anybody fix the example (or the definition) please? Now I see; the example actually works, as edge deletions are included in the definition of subgraph. The explanation of the example is confusing, though.
IMHO, the contractions should be done on the subgraph of G obtained by deleting the "oblique" edges, and so it would be better to use a new image too. fudo (questions?) 13:28, 26 April 2007 (UTC)

I changed the definition so that a minor is a graph that can be obtained by edge contraction on a subgraph. This says deletion but more elegantly. It also points the definition of subgraph for clarification. Flamholz 17:26, 2005 Apr 7 (UTC)

Per the page for planar graph, shouldn't this refer to Wagner's theorem rather than Kuratowski's theorem? -- Sendhil 22:51, 7 July 2006 (UTC)

Fixed --- pom 09:51, 1 September 2006 (UTC)