I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then use Dilworth's theorem. However, every relation I've come up with so far either did not satisfy some properties needed for Dilworth's theorem or seemed to be completely useless. Can anyone point me in the right direction?
Thanks.
No comments:
Post a Comment