Nowadays nobody doubts the significance of the applications of graph theory to other sciences or to real world problems. This workshop emphasizes the diversity of these applications.

However, not everyone outside of graph theory realizes that the powerful combinatorial methods found in graph theory have also been used to prove significant and well-known results in a variety of areas of pure mathematics. That is, that there are applications of graph theory to other areas of pure mathematics as well. Perhaps the best known of these methods are related to matching theory. For example, results from this area can be used to prove Dilworth’s chain decomposition theorem for finite partially ordered sets. A well-known application of matching in group theory shows that there is a common set of left and right coset representatives of a subgroup in a finite group. Also, the existence of matchings in certain infinite bipartite graphs played an important role in Laczkovich’s affirmative answer to Tarski’s 1925 problem of whether a circle is piecewise congruent to a square [1]. Other applications of graph theory to pure mathematics may be found scattered throughout the literature, e.g. see [2]. There, among other examples, matching theory is applied to give a very simple constructive proof of the existence of Haar measure on compact topological groups.

In this talk we will present an examples of such applications of graph theory to number theory, measure theory, and analysis, respectively. On purpose two of these applications are applications of graph theory (finite mathematics) to continuous mathematics, which we find more impressive. Further criteria for choosing these examples were that the theorem is fundamental, widely known, and the graph theory proof of the theorem is the most elegant and/or the shortest one. In other words, the proof should exhibit the strength and elegance of graph-theoretic methods.

References
[1] M. Laczkovich, M. Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem. J. Reine Angew. Math. 404 (1990), 77–117.
[2] L. Lóvasz, L. Pyber, D. J. A.Welsh, and G. M. Ziegler, Combinatircs in pure mathematics, in Handbook of Combinatorics (R.L. Graham, M. Grotschel, and L. Lovasz, eds.), Elsevier, 1996.