Talk:Kőnig's theorem (graph theory)

Use "Kőnig" instead of "König" throughout?

Since this theorem was by a Hungarian named Kőnig, shouldn't the article properly use the double acute accent instead of the umlaut on his name? Just checking here. If nobody objects, I think I'll make the change. Oliphaunt (talk) 09:32, 28 April 2011 (UTC)

I think that the rule is that we use the spelling that is "usually" used in the English language literature. A random look into Math Reviews or Zentralblatt shows that the "König" spelling occurs more often than "Kőnig". (Even though I agree that the latter is more correct, in a sense.) --Aleph4 (talk) 19:59, 9 May 2011 (UTC)

Since our biography of Gyula Kőnig says that he used the umlaut in the pseudonym, "Julius König", which he used when publishing mathematics, I think we should leave it as an umlaut. That is the name he chose to be called by when writing mathematics, and this article is about his mathematics. JRSpriggs (talk) 11:22, 10 May 2011 (UTC)

Ah yes, that would settle the matter. Thanks! Oliphaunt (talk) 12:30, 10 May 2011 (UTC)

I don’t think it does. Gyula Kőnig is the father of Dénes Kőnig whose theorem this article is about. This discussion is duplicated in here. --Nomeata (talk) 16:24, 9 January 2012 (UTC)

Clarification of the Proof

I had problems understanding the instructions on how to partition the bipartite graph. It says

If there are no vertices adjacent to S_2j, arbitrarily pick an unused vertex and continue in S_2j+1.

First, the term "unused" is not immediately clear. I guess an unused vertex is one that is not part of any S_x. Second, "continue in" is not very precise. I guess it should read "insert it in S_2j+1 and again, add its matched neighbors to S_2j+2".

Using the rules above, I partitioned the graph below. The case stated above appears and it shows that the following doesn't always hold.

Each vertex in S_i has an edge to a vertex in S_i−1.

http://anarchistische-musikwirtschaft.de/partitioning.png cw' (talk) 21:12, 17 April 2013 (UTC)

I believe the proof was essentially sound but contained a number of inaccurate or unclear statements, including the ones you quote. I have substantially reworded the proof. Hope it is an improvement. Since I cannot view your diagram, I'm not sure I've addressed your issue. Let me know if you find anything amiss.

Will Orrick (talk) 15:46, 24 August 2013 (UTC)

Unfortunately, it's not an improvement, since the new version of the proof is wrong. The statement that no edge in M can contain both endpoints in K is false. Those vertices in K which are from R are connected to (L \ U) with the edges from M. Please correct me if I'm wrong. Sysoev. — Preceding unsigned comment added by 92.100.249.16 (talk) 21:09, 18 November 2016 (UTC)

I second this. I came here looking for how to convert a solution to the maximal matching into a solution for the minimum vertex cover, and the proof section as of this edit is incredibly difficult to understand for this, only briefly mentioning alternating paths, which are critical for understanding the proof. I understood the topic quickly after reading the revision prior to this change. Therefore I propose that the algorithm that was removed by the edit be re-added in some way that fits with the new version of the article as of 2020. Earthcomputer (talk) 00:31, 18 November 2020 (UTC)

Prior to what change? Can you provide a link to the version you like and identify the paragraphs or sections that you wish to see restored? Will Orrick (talk) 06:19, 18 November 2020 (UTC)

Prior to this change. In particular the alternating path algorithm, along with the diagram on the right. I think it should have been reworded to be clearer, but not entirely deleted as it was. Earthcomputer (talk) 17:48, 18 November 2020 (UTC)

That clears a few things up. The user whose comment you seconded appears not to have checked the page history, as the proof I was talking about had been completely replaced by the current proof at the time they made their comment. I agree that a diagram like the one that was deleted would be nice to have. That particular diagram wouldn't be suitable for the current proof, but it shouldn't be hard to come up with a diagram that would be appropriate. I'm not sure why you find the new proof problematic. The sets $U$, $Z$, and $K$ are all defined by a straightforward algorithm, aren't they?

Since no one has done so previously, I also wanted to point out where user 92.100.249.16's criticism is mistaken. It is true that vertices of $K$ that are from $R$ can be connected to vertices vertices of $L\setminus U$ via edges of $M$. But it will never be the case that vertices of $K$ that are from $R$ are connected to vertices vertices of $L\setminus Z$ via edges of $M$, and it is the latter that is relevant to the definition of $K$. If a vertex of $L$ is in $K$, it's in $K$ because it's not on an alternating path that starts from $U$. If a vertex of $R$ is in $K$, it's in $K$ because it is on an alternating path that starts in $U$. If a matched edge $e$ joined two elements of $K$ it would have to join a vertex in $L$ that isn't on an alternating path starting from $U$ to a vertex in $R$ that is on an alternating path starting from $U$. This is impossible because such an alternating path enters vertices of $R$ via unmatched edges and leaves them via matched edges, and that would make $e$ and hence its endpoint in $L$ a part of the alternating path. Will Orrick (talk) 20:18, 20 November 2020 (UTC)

One possible diagram would be based on the graph shown in the article's introduction. If $L$ is the set of vertices at the bottom, numbered 1 through 7 from left to right, and $R$ is the set of vertices at the top, numbered 8 through 14 from left to right, then $U=\{1\}$, $Z=\{1,10,11,3,5,13,7\}$. The sets $L\setminus Z=\{2,4,6\}$ and $R\cap Z=\{10,11,13\}$ together make up the set $K$ (which consists of the vertices shown in red). Perhaps marking the alternating paths and the set $Z$ would help clarify things? Will Orrick (talk) 00:22, 21 November 2020 (UTC)

Yes, I was particularly confused about the definition of $Z$. An example of each of the sets in the graph at the top of the article, along with brief explanations of how they fit the definitions of the sets in the context of that graph, would help a lot to make this section more readable. Earthcomputer (talk) 01:47, 21 November 2020 (UTC)