Mathematics and Philosophy 2 E-Book

Daniel Parrochia

• Herausgeber: John Wiley & Sons
• Kategorie: Bildung
• Sprache: Englisch

Seitenzahl: 412

Veröffentlichungsjahr: 2023

Beschreibung

From Pythagoreans to Hegel, and beyond, this book gives a brief overview of the history of the notion of graphs and introduces the main concepts of graph theory in order to apply them to philosophy. In addition, this book presents how philosophers can use various mathematical notions of order. Throughout the book, philosophical operations and concepts are defined through examining questions relating the two kinds of known infinities - discrete and continuous - and how Woodin's approach can influence elements of philosophy. We also examine how mathematics can help a philosopher to discover the elements of stability which will help to build an image of the world, even if various approaches (for example, negative theology) generally cannot be valid. Finally, we briefly consider the possibilities of weakening formal thought represented by fuzziness and neutrosophic graphs. In a nutshell, this book expresses the importance of graphs when representing ideas and communicating them clearly with others.

Leseprobe

Graphs, Orders, Infinites and Philosophy

Daniel Parrochia

First published 2023 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

John Wiley & Sons, Inc.

27-37 St George’s Road

111 River Street

London SW19 4EU

Hoboken, NJ 07030

UK

USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2023The rights of Daniel Parrochia to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s), contributor(s) or editor(s) and do not necessarily reflect the views of ISTE Group.

Library of Congress Control Number: 2022948075

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-78630-897-9

Introduction

This book deals with some of the possible applications of mathematics to philosophy. In a previous work (see Parrochia 2018), we have shown how philosophers, from the birth of philosophy in Greece until now, and throughout the complex and sometimes overflowing developments in the history of philosophy, have benefited from the advanced mathematics of their time, which have often inspired them.

We now want to apply this view to today’s mathematics and philosophy. It seems to us that in the great reservoir of mathematical structures, particularly those encountered in graph theory, in the theory of orders (including partial orders), as well as in a number of algebraic or geometric configurations, even infinite ones, current philosophers can find new and revolutionary modes of organization of their own thoughts.

Although the reading of the present text assumes some familiarity with mathematics, we write essentially for the philosophers, or say, for the mathematical philosophers, rather than for the specialists of the fields we mention.

Kant, in the past, considered that the risk of philosophy was to wander in nature, but that, conversely, mathematicians could not find, outside their field, either the earth which could carry them, or the water which allowed them to swim. Everything was like in Ovid’s chaos: instabilis tellus, innabilis unda (see Kant 1922, pp. 582–583)1.

In fact, mathematics is one of the main sources of intelligibility of reality. But its role does not stop there. It can also provide philosophy with more precise concepts than the ones we ordinarily use to interpret the sensible world. As we shall see, discoveries in mathematics sometimes limit or dispute the claims of past doctrines, but they may also suggest new ways of posing problems.

We first wish to illustrate these affirmations by some reflections on graph’s problems, as the mathematicians today conceive them. We will go on by some considerations on order, pre-order and partial order, then carry out more geometric and topological investigations. In the end, we tackle the question of infinity and come to possible applications in our domain of some particular graphs (incomparability, fuzzy, neutrosophic or polyhedral graphs). We only use common notations and remain, the most of the time, as clear as possible, in order to give the philosophical reader some useful tools for developing their own thought.

Let us now define what a “philosophical system” is for us, i.e. the “unit” on which philosophical considerations are based. I emphasize this point: the history of thought, the sociology of knowledge may be concerned with philosophical ideas. But the proper history of philosophy is concerned with systems, or, at least, philosophical constructions which must explicitly explain why they are not – or cannot be – systems.

Definition: We will call a philosophical system a theory, expressed in the common language or a saturated extension of it, which tries to give a conceptual image of the whole world, or eventually explains why such an image is impossible to construct.

Commentary: The sentence “expressed in the common language or a saturated extension of it” allows us to distinguish between philosophy and science. Generally, philosophy is written in a language very close to the natural language and that may be read by everyone. For example, this is the case in Plato’s dialogues, in the works of French authors from the 18th century such as Rousseau and Diderot, or in the essay by Fichte entitled The destination of man. However, in a more elaborated form, philosophy can make use of more or less abstract concepts and sometimes refers to scientific language (see, for instance, the Logical Investigations by Husserl). The expression “saturated extension” comes from logic and was introduced by Jean Ladrière (see Ladrière 1972)2.

Moreover, in order to complete this distinction between science and philosophy, the term “world” has to be interpreted in a larger sense than the term “universe”. Then we can separate philosophy from this branch of physics called “cosmology”. Classical philosophy is a kind of existential cosmology supporting the non-physical dimensions of the world. For a classical philosopher, the universe or, a fortiori, the observed universe, is only a small part of a larger entity that the German-Swiss philosopher Karl Jaspers (1883–1969) named “the Encompassing”3.

In this context, the classic philosophical operation consists of postulating that there exists a mapping:

between a metaphysical entity W, which is supposed to represent the whole world in its complexity4, and a philosophical system S, which captures its main features.

When a philosopher thinks that this operation is impossible, then they generally try to show that, in some particular system SP written by a philosopher P , there exists some linguistic expression x to which P did not give any sense, so we cannot exhibit any corresponding concrete entity in W. In symbols:

Commentary: Following the suggestions of Hume, Kant was probably the first philosopher who applies this method. He proves that we cannot have any knowledge of entities about which we get no information (in his language, no empirical or pure intuitions), so that the three great metaphysical “objects” named God, World and Soul have no corresponding reality in the concrete experience. Wittgenstein pursue this task in his Tractatus logico-philosophicus and began to hunt down all the linguistic expressions that philosophers used in a naive way and that were in the same situation. This project, in a more or less strong form, was thereafter continued by all so-called analytical philosophy.

In this book, we want to explore the actual possibility of constructing today’s philosophies by studying the different forms of organizations that they can take. We will show that mathematics gives a lot of tools to build robust conceptual architectures so that we may hope that systematic philosophy is always possible5.

This undoubtedly rests on several postulates which can be listed as follows:

– (P1) It is possible to represent without bias, in a single form and of limited dimension – what is called a “philosophical system” – the essential of what constitutes our experience of the world.

–(P2) A philosophical system is useful and even necessary (if not, why waste time building it?).

– (P3) The relational structure (generally expressed as a graph6) of a philosophical system is connected in some sense to the relational structure of the world. But the correspondence between them is not an isomorphism – “the map is not the territory”, as Korzybski said (see Korzybski 1933, p. 58) – but probably not even a homomorphism. For example, the structure of the world may be an asymmetric graph, while the structure of the system is symmetric. However, we require the system to represent, without noticeable distortion, the main features of the world of which it is supposed to be an image.

The first two postulates have a methodological character. The latter is clearly ontological.

This latter is probably the most problematic. It has been widely discussed, since the famous article by the American mathematician and philosopher Randal Roy Dipert (1997), of which we would like to say a few words here.

The first part of Dipert’s article (“the shortcomings of logic and logical metaphysics”) is one of the best argued refutations of analytical philosophy that can be found. The second part argues for a well-tempered “relationalism”. But it is especially the third part (“structure, asymmetric graphs and Aristotle refuted”) and the fourth part (“the world as asymmetric graph”) which are the most interesting for our purpose7.

In the third part, after recalling the fundamental definitions of graph theory (simple graph, oriented graph, graph with loops, symmetric or asymmetric graphs, hypergraphs, etc.), Dipert then concentrates on structurally different graphs, i.e. non-isomorphic ones, the number of which grows according to a sequence that approaches asymptotically 2p/2/p!, when p is the number of their vertices. But the subset that interests him is that of non-isomorphic, asymmetric graphs and their subgraphs.

The theory of pure formal structures to which empiricity boils down is that of these non-isomorphic and asymmetric graphs, as well as their subgraphs. And the whole world is, in truth, nothing but an immense asymmetrical graph having a very particular structure, distinct from any other. Against Aristotle who, in Categories 7 (8a 14f–8a 37f) believes to refute relationalism, Dipert claims that asymmetric graphs exclude all kinds of monadism.

In the fourth part, two crucial questions are asked: “First, is it possible that the universe is just a formal structure, and that we can only think about the world as such a structure? Secondly, is it conceivable that the structure that is the world is just a graph-theoretical structure?” The answers to these two questions are positive.

Dipert observes that what the world reduces to is not necessarily a graph with a very large number of vertices. Medium-sized graphs (say between 40 and 100 vertices) already contain a lot of connections. For example, a graph of 40 vertices already contains 240 connections, a number that approximates that of the basic components of our universe or the informational content of it, which by some estimates is roughly equivalent to the number of non-isomorphic graphs of order 40.

The link with physical “theories of everything” is as follows: physical objects, including elementary particles – which are in fact composite – do not correspond to vertices of the graph but to subgraphs. The physical microstructure is in fact a theoretical macrostructure from the graphic point of view. As for space and time, they correspond to frames or grids which are in fact families of paths (symmetrical for space, asymmetrical for time). Forces, fields and causal chains are also such paths among subgraphs that are identified as physical objects.

Naturally, the mind and its thoughts must have their place in this graph which thus includes in itself a mirror structure. As Dipert wrote:

thoughts are about a phenomenon – refer to it – if they occupy a certain place in the world graph (in a “mind”) and share certain structural features with the thought-about object: a thought, per impossible, is perfectly about an object just when its internal graphical structure is the same as the object’s, and when the object occupies a location in the system of all objects that is like the thought’s location in the system of (that mind’s) thought (Dipert 1997, p. 357).

We might think then that, in such a theory, there is no room for minds, consciousness and other mental phenomena, unless, precisely, everything is mental, which finally, Dipert, following in this Leibniz, if not Spinoza, does not entirely exclude, because the vertices of the graph could, after all, only be “feelings”.

This remarkable article surely unleashed the hostility of the philosophers who prefer Aristotelian matter to formal structures and the sentimental illusion of human warmth to the objective relationships depicted in this cold graph. But the strongest objection, developed in a short article by Oderberg (2011, pp. 6–9), was based on a mathematical argument that Shackel (2011, p. 11) very well summarized as follows:

1) suppose the world is a graph;

2) if it is a graph, it is an asymmetric graph;

3) any asymmetric graph can be turned into symmetric graph by the removal of edges;

4) the loss of less than all the edges of the world (specifically, the loss of all those not part of some symmetric subgraph, a loss consequent on certain nodes going out of existence) metaphysically entails the non-existence of the entire world (1, 2, 3);

5) Therefore, the world is not a graph (1, 4, reductio ad absurdum).

In fact, this mathematical argument is quite specious: why imagine that the asymmetric graph of the world could become symmetrical? As Shackel writes, “it’s impossible for the world graph to be other than it is and hence any change at all entails non-existence” (Shackel 2011, p. 13), so Oderberg’s objection is not a valid argument: “it is impossible to get rid of the nodes and edges of a world and the argument to the absurd inexistence is blocked” (Shackel 2011, p. 14).

The fact remains that the necessity of Dipert’s structure may seem troublesome. However, reducing the properties to simple potentials, as Bird could have done in another model (see Bird 2007), would not remove the problem according to Oderberg. Because if there is only potential and no actualization, then nothing can really manifest itself, as he also explains in another article (see Oderberg 2012). But, as Shackel shows, there are potency graphs for which a diffusion process gradually updates some (or all) of the potentials. The phenomenon is a “snowball” and we can demonstrate that, in this type of graph (snowflake graphs), we can always choose a node from which all the potentials can be actualized.

In conclusion, Dipert’s graph is perfectly plausible and this possible reduction of the world to a graph makes it possible, as well, to somehow ontologically base the attempts of philosophers over time. If it is rejected, however, it cannot be denied that these attempts can be methodologically described using the formalism of graph theory. So we do not absolutely need the assumption P3 to justify what follows.

However, if we accept to consider the world as a graph, then, if the world is finite, there is a good chance that its graph is asymmetric. Indeed, the proportion of graphs on n vertices with non-trivial automorphisms tends to zero when n grows, which informally means that almost all finite graphs are asymmetric. In contrast, almost all infinite graphs are symmetric and, more specifically, countable infinite random graphs in the Erdös–Rényi model are, with probability 1, isomorphic to the highly symmetric Rado graph (see Erdös and Szekeres 1935).

In this text, using the language of graphs, orders and sometimes infinites, we try to represent mathematically this entity that Jaspers called “the encompassing”, and which he thought it was, by definition, impossible to objectify.

In fact, mathematics has often taught us that it is possible to obtain good characterizations of an object without having to bring it in any exteriority. As Gauss showed in the case of surfaces (theorema egregium), it is very remarkable that the curvature of a geometrical object can be described intrinsically, i.e. without any reference to a “space of embedding” in which the considered object would be located. For example, the fact that an ordinary sphere is a surface with constant positive curvature is completely independent of the fact that we usually see this sphere as being immersed in our three-dimensional Euclidean space. The curvature of this sphere could very well be measured by two-dimensional intelligent beings living on the sphere (kinds of “two-dimensional ants”), from measurements of lengths and angles carried out on the sphere.

We must imagine that we are, with respect to the encompassing, in the same situation as two-dimensional ants with respect to the sphere. In principle, nothing prevents us from being able to describe it if we have the necessary information.

Notes

1

Kant was exactly speaking of “the uncertain ground of pure and ever, transcendental concepts (instabilis tellus, innabilis unda) where they are neither able to stand nor to swim, taking only a few hasty steps, the vestiges of which are soon swept away” (in German: “wo der Grund (instabilis tellus, innabilis unda) ihnen weder zu stehen, noch zu schwimmen erlaubt, und sich nur flüchtige Schritte tun lassen, von denen die Zeit nicht die mindeste Spur aufbehält”). The implicit reference to Ovid refers to

Metamorphoses

, I, 15: “Utque erat et tellus illic et pontus et aer, sic erat instabilis tellus, innabilis unda, lucis egens aer”. In English: “Though there was land and sea and air, it was unstable land, unswimmable water, air needing light”.

2

To keep it simple and not get into too technical considerations of model theory, we can say that a logical system is

saturated

if any addition of a supplementary thesis makes it contradictory or, if it tolerates certain forms of contradiction in itself, inconsistent with respect to a particular operation different from classical negation.

3

Because of the subject–object split, which always places our consciousness outside the world of objects, being as a whole can be neither object nor subject. According to Jaspers, it must be the “encompassing” that manifests in this split. Objects as subjects therefore arise against the background of this encompassing, which remains partly obscure. It is clarified only by objects, and it becomes all the more clear as the objects are more clearly present to consciousness. But, for all that, it does not itself become an object. It is therefore basically what, through thought, only announces itself. We never meet it itself, but everything we do meet, we meet in it.

4

This complexity is assumed, but it is not yet known when the philosopher begins their work. In order to justify the possibility of this operation, some philosophers like M. Gueroult have spoken of this entity

W

as a “common real” (see Gueroult 1979). Others have simply postulated that there is, in everyone, a “thought of a frame of reference” (see, for example, Granier 1977).

5

This project must not be considered as an utopy or an old-fashioned dream. From Whitehead to Rescher, the idea of cognitive systematization has continued, as, moreover, it persists in our everyday life when we try to understand this one in all its aspects.

6

Let us just say here, to fix ideas, that it is a set of vertices connected by arcs or edges, depending on whether the graph is directed or not.

7

The reader can find the complete definition of symmetric and asymmetric graphs in

section 1.8

.

1Graphs

This chapter is an introduction to our subject. After a few words about the history of graphs, we explain what we now call a “graph” in mathematics and introduce the main definitions useful to understand what follows. Then, we study some particular classes of graphs that we can meet in philosophy and give some examples of them.

1.1. Graph theory: a brief history

The origin of graph drawings is not well known, but we have already found some of them in ancient China.

As in the terrestrial order, where the ancient Chinese used cryptography to restrict the transmission of certain messages to the initiates, communication with the heavenly forces required in China a form adapted to the addressee, and conversely the message of celestial forces could not take over the form of a terrestrial message. Thus came the fu, these graphs, most often Daoist, which allowed followers to enter into communication with spirits and spirits to communicate with the earthly world (see Figure 1.1).

In this region of the world, some graphic constructions may also be found in decorative motives of architecture or jails (see Figure 1.2) which follow certain logics (He and Schnabel, 2018).

Figure 1.1.Taoist Fu surmounted by a constellation of 5 stars (right); official of fate (left) (BNF, Coins, Medals and Antiques - CF A-135)

(source: BNF)

Figure 1.2.Chinese decorative graphs

(photo: Z. Guo)

It seems that one of the earliest forms of them in western countries are probably that of Morris and Mill games, as shown in Figure 1.3, where the nodes of the graph drawing are the positions that game counters can occupy, the edges indicating how game counters can move between nodes (see Kruskal 1960, pp. 272–286).

Figure 1.3.Depiction of Morris gameboards

The origin of Mill gameboards comes from stone carvings in Ancient Egypt but the date of the earliest examples of Mill gameboards to be drawn in a book only goes back to the end of the 13th century.

However, early graph drawings were not exclusively an invention of Asia or the Middle East.

Quipus, which are bundles of cords whose knots and combinations replaced the writing (see Figure 1.4), were used by the Incas from the 13th to 16th centuries for accounting purposes and especially to register important facts and events. Of the few hundred surviving examples, roughly 25% exhibit a hierarchical structure and therefore qualify as tree drawings (see Ascher and Ascher 1997).

Figure 1.4.Incas’ quipu

(source: Wikipedia article: Quipu)

Another example of ancient graph drawings is family trees which decorated the atria of the patrician roman villas. Though no example has survived, it has been described by Pliny the Elder and Seneca. It was not until the Middle Ages that we saw them reappear.

During the 14th century, there appeared trees depicting the categories of different kinds (vices, virtues), while logicians often use them to represent abstract information (Porphyrian tree) or to illustrate the system of logical arguments (square of opposition).

After that, nothing comes before the famous paper of 1736 written by Leonhard Euler on the seven bridges of Kœnigsberg1 and regarded as the first paper in the history of graph theory (see Biggs et al. 1986; Parrochia 1993b). This paper, as well as the one written by Vandermonde on the knight problem in chess, carried on with the dream of the so-called “analysis situs” initiated by Leibniz and the ancestor of topology.

Euler’s formula relating the number of edges, vertices and faces of a convex polyhedron was studied and generalized by Cauchy (1813) and L’Huillier (1812-1813) and represents the beginning of this new branch of mathematics: algebraical topology.

More than one century after Euler’s paper and while Listing was introducing the concept of topology, Cayley was led by an interest in particular analytical forms arising from differential calculus to study a particular class of graphs, the trees (see Cayley 1857). This study was partly motivated by important problems in theoretical chemistry. The techniques Cayley used mainly concerned the enumeration of graphs with specific properties. Enumerative graph theory then arose from his results and also the fundamental results published between 1935 and 1937. These were then generalized by De Bruijn in 1959. The links established by Cayley between his results on trees and contemporary studies of chemical composition (see Cayley 1875) influenced the development of a standard terminology in graph theory.

For example, the term “graph” was introduced by Sylvester in a paper published in 1878 in Nature, where he draws an analogy between “quantic invariants” and “co-variants” of algebra and molecular diagrams (see Sylvester 1878):

Every invariant and co-variant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph. I give a rule for the geometrical multiplication of graphs, i.e. for constructing a graph to the product of in- or co-variants whose separate graphs are given.

The first textbook on graph theory was written by Dénes König and published in 1936 (see König 1990). Another book by Frank Harary, published in 1969, was “considered the world over to be the definitive textbook on the subject” (see Gardner 1992, p. 203) and enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other. In France, Claude Berge (see Berge 1970) has also published in the 1970s a very important book about graphs and hypergraphs.

Let us now enter some particular problems in graph theory.

One of the most famous and stimulating problems in this field is the four color problem: “Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?” This problem was first posed by Francis Guthrie in 1852 and its first written record is in a letter of De Morgan addressed to Hamilton the same year. Many incorrect proofs have been proposed, including those by Cayley, Kempe and others. The study and the generalization of this problem by Tait, Heawood, Ramsey and Hadwiger led to the study of the colorings of the graphs embedded on surfaces with arbitrary genus. Tait’s reformulation generated a new class of problems, the factorization problems, particularly studied by Petersen and König. The works of Ramsey on colorations and more specially the results obtained by Turán in 1941 were at the origin of another branch of graph theory, extremal graph theory.

The four-color problem remained unsolved for more than a century. In 1969, Heinrich Heesch (see He and Schnabel 2018) published a method for solving the problem using computers. A computer-aided proof produced in 1976 by Kenneth Appel and Wolfgang Haken makes the fundamental use of the notion of “discharging” developed by Heesch (see Appel and Haken 1977a, 1977b). The proof involved checking the properties of 1,936 configurations by computer, and was not fully accepted at the time due to its complexity. A simpler proof considering only 633 configurations was given 20 years later by Robertson et al. (1997).

The autonomous development of topology from 1860 to 1930 fertilized graph theory back through the works of Jordan, Kuratowski and Whitney. Another important factor of common development of graph theory and topology came from the use of the techniques of modern algebra. The first example of such a use comes from the work of the physicist Gustav Kirchhoff, who published in 1845 his Kirchhoff’s circuit laws for calculating the voltage and current in electric circuits.

The introduction of probabilistic methods in graph theory, especially in the study of Erdös and Rényi of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as random graph theory, which has been a fruitful source of graph-theoretic results.

The consideration of flows and networks and the development of the Ford–Fulkerson method provide a new approach in graph theory, combinatorics and then algorithmics.

We will first explore the already large universe of graphs.

1.2. Basic definitions

Let us begin with some definitions.

DEFINITION 1.1.– In its modern mathematical sense, a graph is an ordered pair G(V, E) comprising a set V of vertices or nodes or points together with a set E of edges or arcs or lines, which are 2-element subsets of V (i.e. an edge is associated with two vertices, and that association takes the form of the unordered pair comprising those two vertices). This is not exactly, indeed, the most general definition. To avoid ambiguity, we will see later that this type of graph may be described precisely as undirected and simple. This characteristics are sufficient for the moment.

REMARK 1.1.– The vertices belonging to an edge are called the ends or end vertices of the edge. A vertex may exist in a graph and not belong to an edge.

REMARK 1.2.– The sets V and E are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case.

DEFINITION 1.2.– The order of a graph is |V |, its number of vertices. The size of a graph is |E|, its number of edges. The degree or valency of a vertex is the number of edges that connect to it, where an edge that connects a vertex to itself (a loop) is counted.

For an edge {x, y}, graph theorists usually use the somewhat shorter notation xy.

1.3. Different types of graphs

As we have seen, many graphs have been discovered throughout the history of the discipline, so that today, even restricting us to interesting or well-known graphs, which are already very numerous, we are dealing with an extremely large set, in fact a very bushy forest, not to say a real jungle.

Exploring this collection supposes that we have identified some distinctive features that can guide us and allow us to define classification criteria.

There are, in fact, various types of graphs depending upon the number of vertices, the number of edges, their interconnectivity and their overall structure. We will discuss only a certain few important types of graphs in this chapter.

DEFINITION 1.3 (NULL GRAPH).– A graph having no edges is called a null graph.

Philosophical example: At the end of his book The Unique and His Property,the hymn to egoism, the notion that the individual is the measure of all things, Max Stirner states “that the individual is a world history for himself, and possesses his property in the rest of the world’s history”. It ensures “that every higher essence above be it God, be it the human being, weakens the feeling of my uniqueness, and only before the sun of this awareness”. On the contrary, he assures: “If I base my affair on myself, the unique, then it stands on the transient, the mortal creator, who consumes himself, and I may say: I have based my affair on nothing” (see Stirner 2017, pp. 376–377). We cannot better illustrate both the idea of a graph with a single vertex and the denomination of this one as “null graph”.

DEFINITION 1.4 (TRIVIAL GRAPH).– A graph with only one vertex is called a trivial graph.

Philosophical example: The circular J − set, with one vertex and one loop, in Finsler’s theory of sets (see Booth and Ziegler 1996), is a beautiful example of trivial graph2.

DEFINITION 1.5 (NON-DIRECTED GRAPH).– A graph which contains edges but in which the edges are not directed ones is a non-directed graph.

DEFINITION 1.6 (DIRECTED GRAPHS).– A graph in which each edge has a direction is a directed graph (sometimes, it may be called a network).

DEFINITION 1.7 (SIMPLE GRAPH).– A graph with no loops and no parallel edges is called a simple graph.

DEFINITION 1.8 (REGULAR GRAPH).– A graph G is said to be regular, if all its vertices have the same degree. In a graph, if the degree of each vertex is k, then the graph is called a k-regular graph.

DEFINITION 1.9 (COMPLETE GRAPH).– A simple graph with n mutual vertices is called a complete graph and it is denoted by Kn.

REMARK 1.3.– In other words, if a vertex is connected to all other vertices in a graph, then it is called a complete graph.

DEFINITION 1.10 (CYCLE GRAPH).– A simple graph with n vertices (n ≥ 3) and n edges is called a cycle graph if all its edges form a cycle of length n.

DEFINITION 1.16 (STAR GRAPH).– A complete bipartite graph of the form K1,n−1is a star graph with n vertices. A star graph is a complete bipartite graph if a single vertex belongs to one set and all the remaining vertices belong to the other set.

1.5. Graphs and vertices