0
$\begingroup$

I'm writing a MIZAR article about foundations in graph theory e.g. constructing a supergraph from a given graph by adding a vertex to it. The main theorem of the article will be that any graph drawable by hand (i.e. with finitely many vertices and edges) actually exists mathematically and can be constructed inductively.

Question: Is there any literature where these "obvious" questions have been studied? I'm looking for references. Any textbook I encountered just gave one mathematical definition of graphs (e.g. pair of vertex set and subset of the set of all 2-element subsets of the vertex set) and then just printed examples in picture form. A more concrete example: the path graph ._ ._ ._ ... _. is often pictured, sometimes with length $n$ as I just did, sometimes with certain lengths to avoid "..." in the pictures. Sometimes it is said to be constructed by starting with the trivial graph and just adding an edge and vertex to one of its endpoints, which is closest to a formal definition of the path graph, but the process of this adding itself is never justified, allegedly because it is so obvious. But set theory was obvious too for quite some time, so I'm hoping something has been done on this matter. On the other hand, of course it would be quite fulfilling to be a pioneer in this field, but frankly I don't want to end up writing things like "a topic that is so natural to mathematicians that hardly anyone bothers to mention it explicitly at all".

For me to know that I should have read a lot of books of graph theory and I haven't. Most are for undergraduate students in mathematics and computer science and are all quite similar. Even advanced books like "Selected topics in graph theory" (Ed. Lowell W. Beineke, 1978) don't cover this subject. So I'm hoping someone here knows such a book or paper by chance.

Meta-Discussion if off-topic or not

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ It is still rather unclear to me what you are looking for. What does it mean for a graph to "exist mathematically"? The way I read your question, your "Theorem" is that for any finite graph $G$ there exists a sequence $G_0, G_1, \ldots, G_n$ of graphs $G_i$ such that $G_0$ is the empty graph, $G_n = G$ and $G_{i+1}$ is obtained from $G_i$ by adding a single vertex and some edges to vertices of $G_i$. But that seems to be a triviality, unless you work in some severely restricted logical universe. Please clarify what you have in mind. $\endgroup$
    – monkeymaths
    Commented Dec 31, 2017 at 12:37
  • 3
    $\begingroup$ I'm sorry, I still do not see the hidden complexity you refer to. More concretely, what's wrong with (1) Defining induced subgraphs (very easy in the "$G = (V,E)$" set-up) (2) Enumerating the vertices of $G$ as $v_1, \ldots, v_n$ and taking $G_i$ as the subgraph induced by $\{ v_1, \dots, v_i\}$? $\endgroup$
    – monkeymaths
    Commented Jan 7, 2018 at 17:42
  • 1
    $\begingroup$ @monkeymaths Because you don't start with the finished graph on paper and remove edges and vertices until you're left with a blank sheet, the process is the other way around. More scientifically, try to proof that adding an edge between two vertices where you just deleted an edge returns the original graph. Even when you define "adding an edge" as the reverse operation of removing one, you still need to show that there always exists a super graph where you can get the current graph from by removing an edge. Leads to the same definitional problem, no? $\endgroup$
    – SK19
    Commented Jan 9, 2018 at 10:21
  • 3
    $\begingroup$ If a graph is a pair $(V,E)$, then for each $x\not\in V$ and every $A\subseteq V$ one can form the pair $(V\cup\{x\}, E\cup\{\{x, a\}:a\in A\})$. The existence of these objects follows from basic set theory, e.g. ZF. So adding a vertex is no problem. Adding and deleting edges is even easier. Proving that deleting an edge and then adding this edge gives the same graph is equivalent to $(E\setminus\{\{u,v\}\})\cup\{\{u,v\}\}=E$, which is again basic set theory. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Jan 13, 2019 at 11:31
  • 1
    $\begingroup$ I edited to add the [reference-request] tag, since that is key to what you're asking. [textbook-recommendation] is probably not what you want, since that seems to be generally used specifically for textbooks qua teaching materials. $\endgroup$
    – David Roberts ♦
    Commented Jan 16, 2019 at 1:25

1 Answer 1

Reset to default
1
$\begingroup$

The article has been finished and since I couldn't find any reference to this basic research I guess I provided the first reference :-)

Sebastian Koch, About Supergraphs. Part I, Formalized Mathematics, 26 (2) (2018) pp 101–124, doi:10.2478/forma-2018-0009

Improve this answer
$\endgroup$
1
  • 8
    $\begingroup$ Just providing a publisher spaghetti url to a web-displayed pdf is about the worst kind of reference. If de Gruyter changed their system in a stupid way (like eg Springer and Elsevier have in the past) no one would be able to track down the article without some effort. I added a proper citation plus the doi link which is the best sort. $\endgroup$
    – David Roberts ♦
    Commented Jan 14, 2019 at 23:50

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