57
$\begingroup$

I read the Wikipedia articles for both topology, graph theory (plus topological graph theory). Does topology encompass also graph theory? Or topology is only about studying shapes while graph theory is about relations and the two meet in topological graph theory?

$\endgroup$
1

5 Answers 5

33
$\begingroup$

There are (at least) two ways to answer this question. In the strict definitional sense, you can probably get all of graph theory expressed in the language of topology. If you're really sneaky you can probably do it the other way, too, so you could probably have a good time claiming that "all of graph theory is just part of topology", and likewise "all of topology is just part of graph theory".

However, more importantly I think, the flavour of the two fields are typically quite different. By this I mean, if you happen upon a mathematician these days that considers herself a topologist, chances are she works either on something geometric, or very algebraic, and either way something pretty abstract. On the other hand, if you happen upon a mathematician that considers herself a graph theorist, chances are she works on some pretty concrete objects, possibly with more obvious direct connections to real world applications.

The exceptions to that paragraph are numerous, but sort of prove the rule. There are plenty of topologists that work on very concrete objects, and plenty of graph theorists whose work is very abstract or use tools from algebraic geometry, number theory, etc.

Nonetheless, it's unlikely the two will share much overlap in their mathematical interests, and if they do, you would probably call their shared interest topological graph theory, or combinatorial topology. So, I think your last statement is closest to the truth, although I'd say topology is much more than studying shapes, and graph theory is much more than studying relations ( or at least doesn't reel like you're studying relations when you're doing it ). Examples are probably the best way to demonstrate that, but then this answer will get way too long, and you're better off just reading/doing some of each to get a feeling for what each field is about.

$\endgroup$
3
  • 1
    $\begingroup$ can you perhaps elaborate (or give a hint) on how to encode any topology graphs and vice versa? $\endgroup$ Oct 10, 2013 at 6:40
  • $\begingroup$ I think my point was missed about that, and better elaborated in your answer. While I suspect it's possible, I don't think it's interesting. More importantly, as you point out, there doesn't seem to be a canonical way to go either direction, making the exercise unlikely to bear fruit. Have said that, bof gives some examples below of how one might go in either direction. In both of his descriptions I could complain "you're excluding this whole important area of graph theory! ( resp. topology )", and I'm sure he could change his descriptions to fit that area, and I'd find another omission etc. $\endgroup$ Oct 10, 2013 at 7:52
  • 1
    $\begingroup$ I'd wager on the impossibility of refining the description to solve the exclusion of most interesting aspects of topology/graph theory by graph theory/topology. But other than that, we agree. $\endgroup$ Oct 10, 2013 at 7:55
27
$\begingroup$
  1. Someone famously called graph theory "the slums of topology" or something like that, but I wouldn't take that too seriously.

  2. Graphs are one-dimensional topological spaces of a sort. When we talk about connected graphs or homeomorphic graphs, the adjectives have the same meaning as in topology. So graph theory can be regarded as a subset of the topology of, say, one-dimensional simplicial complexes. While graph theory mostly uses its own peculiar methods, topological tools such as homology theory are occasionally useful.

  3. A connected graph has a natural distance function, so it can be viewed as a kind of discrete metric space. So graph theory can be regarded as a subset of the topology of metric spaces.

  4. The Tychonoff product theorem of general topology has application to some questions about infinite graphs, as may be seen in the answer to this question.

  5. A topological space is defined by points and open sets. It could be construed as a bipartite graph: the points are vertices in one partite set, the open sets are vertices in the other partite set, and each open set is joined by edges to its elements. But this is crazy.

  6. Certain weird counterexamples in general topology are constructed by topologizing the space of maximal independent subsets of an infinite graph.

  7. Topological graph theory is something else again. Graphs are considered as embedded in or drawn on a topological surface, leading to such concepts as planarity and the genus of a graph.

$\endgroup$
5
  • $\begingroup$ Is it safe to say then that the application of topology to graph theory is only "interesting" when the graph is infinite? $\endgroup$
    – cantorhead
    Jan 15, 2017 at 16:15
  • $\begingroup$ I should rephrase previous comment since one application of topology to graph theory occurs when one attempts to embed the graph in another topology. What I mean to say is, that using edges to define a basis of open sets and extending that basis to a topology is not extremely useful unless the graph is infinite. Is this more accurate? $\endgroup$
    – cantorhead
    Jan 15, 2017 at 17:17
  • $\begingroup$ I think it is just very common to take thermodynamic limits, particularly because asymptotic results are key for a number of reasons related to the applications of combinatorics. For example there are sharp phase transitions, and also asymptotic structures. $\endgroup$
    – apg
    May 19, 2017 at 5:29
  • $\begingroup$ Related to 2.: en.wikipedia.org/wiki/Graph_(topology) $\endgroup$
    – jskattt797
    May 18, 2020 at 3:37
  • $\begingroup$ How is 5 a topological space? The condition includes that all open sets formed by union and complement (which includes intersection) be neighborhoods. In this case there will be more vertices than intended $\endgroup$
    – Nick
    Jul 20, 2021 at 14:32
17
$\begingroup$

I think the most obvious comparison between the two is that a graph is just a 1-dimensional simplicial complex, and algebraic topology is the study of simplicial complexes (or more properly of modern refinements of the idea of a simplicial complex).

In other words, graphs have only vertices and edges, whereas in topology we also add faces and so forth.

$\endgroup$
2
  • 2
    $\begingroup$ The geometric realizations of graphs that are very different may be homeomorphic. Thus, the algebraic topology approach to graph theory looses a lot of information in the graph. For instance, how do you speak of the number of vertices in a graph? The degree of a vertex? you simply can't see these things in the geometric realization. $\endgroup$ Oct 10, 2013 at 7:36
  • 1
    $\begingroup$ True. I guess I'd be inclined to call someone who studies simplicial complexes not up to homeomorphism an algebraic topologist, though maybe that's wrong. I guess a lot of people also feel that "actual" topological properties need to be preserved up to homotopy, not just homeomorphism. $\endgroup$ Mar 6, 2014 at 4:15
12
$\begingroup$

Graph theory and topology, while they certainly enrich each other, are quite different subjects. A graph is a discrete object with many variants. It can be directed or undirected, it can have multiple edges between two vertices or it may not. Typical questions about graphs tend not to be of a local nature. A topological space on the other hand is a geometric object that is designed to capture the notion of continuity. Many of the aspects of topology are of a local nature. Moreover, the directed aspect of graphs does not really have a well-developed theory, or at the very least there is no commonly accepted theory of directed topological spaces.

So, while there are similarities, the differences are huge. There are several different ways to construct a topology out of a graph, and likewise, there is no canonical construction of a graph from a topological space.

$\endgroup$
12
$\begingroup$

Interesting observation: often both disciplines (graph theory, topology) claim that the famous The Seven Bridges of Königsberg Problem solved by Euler in 1736 [1] is one of the first papers of their respective discipline.

So, not so different after all ^^

[1] Euler, Leonhard: Solutio problematis ad geometriam situs pertinentis

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .