What is Graph Theory, and how is a graph defined as such?

In 1736, based on the work of the Swiss physicist-mathematician Leonhard Euler (1707-1783), it was observed that a succession of vertices defines a path, however, if said path consists of different vertices without repeating edges, it is called a path or path eulerian; if additionally we arrive at the starting point, traversing each edge only once, then we have an Eulerian cycle (circuit).

Quote (APA)

alexander barraza | Jul. 2022
Degree in physics

For its part, we define a graph as an ordered pair (GOES) where v designates the (nonempty) set of all vertices or nodes of a graph, while A designates the set (it can be empty) of all the edges or lines that join the vertices of a graph. The elements of the set A can be designated as an unordered pair {v, w} where v and w are elements (nodes or vertices) of v, in this way it is then said that v and w are adjacent vertices (they are joined by an edge).

Graph theory arises from the answer given by Euler to a problem of popular ingenuity that wondered how to cross the seven bridges that joined two islands of the community of Königsberg (part of Germany at the time, and currently Kaliningrad, in Russia), between them and with mainland without using two times the same bridge and arriving at the starting point (located on the mainland) whatever it may be, determining that in this case, ultimately, no could.

The problem of the seven bridges of Königsberg

Euler modeled Königsberg as a graph where each point (vertex or node) represents a bridge and each line (edge) a path on land:

What is the solution to this problem?

there isn't one solution that meets the imposed conditions, since, as Euler showed, the vertices are not of even degree, that is, an even number of lines does not affect each point _[3]. It doesn't seem like we can do much with a structure defined as simply as this, however, as is often the case in math, Sometimes things are not what they seem. Thus, one of the most prolific, transversal and interdisciplinary areas _[4] of human knowledge, graph theory.

Eulerian graphs or with Eulerian trajectory?

The following graphs all have Eulerian paths _[5]. Do they all have Eulerian cycles?

Let's take the third graph:

Let's number the vertices:

We see then that the path defined by the sequence {3,4,6,2,1,3,7,6,5,4,2} is an Eulerian path, since it goes through the entire graph without repeating edges, but it is not an Eulerian cycle, since it does not reach the starting point. What would have happened if we numbered the vertices differently? Not much, except that now the path would be defined by a different succession. What would have happened if we followed different paths than the one proposed in our initial solution? This question is a bit more complex to answer, and it involves algorithms that software engineers are usually delighted with. programming.

For a more rigorous proof of what is exposed here we have to refer to the following result:

"Be G a connected graph _[6]. Then yes G have a circuit Euler, the degree of each vertex is even, while if G has an Euler path, G has exactly two vertices of odd degree _[7] (exactly the vertices where the path starts and ends)".

We can then verify that, in fact, in the graph we take, only vertices 3 and 6 have an odd degree (this would occur even if the numbering of vertices had been different), therefore said graph has a path eulerian _[8]. For the remaining graphs we can proceed in an analogous way and verify if indeed they have paths and Eulerian cycles, or put another way, can we draw such graphs without picking up the pencil and repeating lines? The answer to this question can be deduced from what has already been explained so far, however, it constitutes an exercise interesting in terms of fine motor skills, ingenuity and patience, I invite the reader to find and draw graphs of 6 or more vertices with trajectory Eulerian.

Are there other types of graphs? Does graph theory have applications in the 'real' world?

These graphs that we have reviewed very briefly, are just one of the many types of graphs that we find in graph theory. We can also find graphs such as trees, very representative in sets where their elements can be classified in hierarchies and in counting calculations and probability_[9], digraphs, Hamiltonian graphs _[10], etc.

Image of Graphic Models and Networks in Psycho., by Ruiz, Ana María.

These enigmas, if we want to call them that, have enormous applicability in today's world, in situations as diverse as: biology molecular _[11], computing_[12], telecommunications _[13] and network analysis _[14]. It is worth asking then: Isn't it at least curious that a problem of an almost banal will end up being one of the most interesting and conspicuous results of mathematics? Perhaps, for this, the contribution of one of the most illustrious minds of humanity was necessary.