Questions tagged [graph-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
35 views

What is the earliest paper in which local edge connectivity was defined?

Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. The Local edge connectivity $\lambda(x,y;G)$ for $x,y\in V$ with $x\neq y$ is defined as the least number $|F|$ such that $x$ and $y$ ...
MMM's user avatar
  • 11
1 vote
0 answers
97 views

Was the "Gauss word realization problem" a kind of unknotting problem?

In Moritz Epple's article "Geometric Aspects in the Development of Knot Theory", Epple writes the following: It has been suggested that one of the earliest tools of combinatorial knot ...
user2554's user avatar
  • 4,419
1 vote
1 answer
46 views

What is the earliest paper in which graph vertex connectivity is denoted by the Greek letter $\kappa$?

I'm wondering how far back this notation goes. Thank you for your consideration.
Bilal Khan's user avatar
4 votes
1 answer
649 views

Exact source that Descartes had observed that $V-E+F=2$ for planar graphs

In recent literature, I have read that René Descartes had observed that $V-E+F=2$ for planar graphs. Is there any image of that page of book or article of Descartes? Seeing real page that contains the ...
C.F.G's user avatar
  • 171
0 votes
0 answers
87 views

What does P. G. Tait mean by "double points"?

I am reading the following short paper: P. G. Tait. Some elementary properties of closed plane curves. Messenger (2) 6 (1877), 132–133. JFM 09.0393.01 Here, Tait writes The closed curves ...
The Amplitwist's user avatar
5 votes
0 answers
217 views

Why are there relatively many Eastern European (specifically Hungarian) graph theorists?

I noticed that a large number of theories within graph theory are from Eastern European graph theorists, specifically Hungarian graph theorists. What is the relation between Eastern Europe (...
Kroko's user avatar
  • 51
8 votes
1 answer
758 views

Was a mathematical connection involved when introducing "graph" of a function and "graph" in graph theory?

A colleague and I were having a discussion about mathematical similarities between graphs of functions and graphs as used in graph theory: Simple graphs can be defined in terms of pair (of vertices), ...
Steve Costenoble's user avatar
5 votes
0 answers
191 views

Who coined the term: "Directed Graph"?

I found that the term "Digraph" was coined in 1955 by Frank Harary in "The number of linear, directed, rooted, and connected graphs", and that it was a term actually suggested by ...
Nau's user avatar
  • 233
5 votes
1 answer
186 views

Where can I find the complete papers of abstracts published by P. G. Tait in Proc. Roy. Soc. Edinburgh in 1880?

I am interested in looking up P. G. Tait's flawed proof of the four-colour theorem, published in 1880. The citation that I have seen is: P. G. Tait, On the colouring of maps, Proc. Roy. Soc. ...
user avatar
4 votes
1 answer
547 views

Who was Fleury? And what was his first name?

One of the algorithms for finding Eulerian paths and circuits in graphs that have them is due to Fleury. Lucas mentioned this in his 1892 recreational mathematics collection, referring to "M. ...
Brian Hopkins's user avatar
3 votes
1 answer
135 views

Was there a continuation to the Seven Bridges of Königsberg problem between Euler and Hamilton?

Since Euler's result on the Seven Bridges of Königsberg problem appears to be the first known graph theoretical result I was wondering if any mathematicians after Euler and before Hamilton commented ...
GEP's user avatar
  • 1,515
9 votes
1 answer
1k views

What was the origin of the Seven Bridges of Königsberg problem before Euler?

I was researching the mathematics of this puzzle and wondered where it is be thought to originate. Any information, including context and precedents, would be greatly appreciated. (I'm particularly ...
DukeZhou's user avatar
  • 285