New proofs of Konig's bipartite graph characterization theorem

Salman Ghazal

Abstract


We introduce four new elementary short proofs of the famous K\"{o}nig's theorem which characterizes bipartite graphs by absence of odd cycles. Our proofs are more elementary than earlier proofs because they use neither distances nor walks nor spanning trees.

Keywords


bipartite graph; odd cycle; path

Full Text:

PDF

DOI: http://dx.doi.org/10.19184/ijc.2017.1.2.4

References

D. Ko ̈nig, Theorie der endlichen und unenlichen Graphen, Akademische Verlagsgesellschaft (1936).

R.Diestel, GraphTheory, Graduate Texts in Mathematics (2005). Springer. ISBN 978-3-642- 14278-9


Refbacks

  • There are currently no refbacks.


ISSN: 2541-2205

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View IJC Stats