<abstract xmlns="http://www.w3.org/1999/xhtml">Drawing a finite graph is usually done by a finite sequence of the following three operations.1. Draw a vertex of the graph.2. Draw an edge between two vertices of the graph.3. Draw an edge starting from a vertex of the graph and immediately draw a vertex at the other end of it.By this procedure any finite graph can be constructed. This property of graphs is so obvious that the author of this article has yet to find a reference where it is mentioned explicitly. In introductionary books (like <xref ref-type="bibr" rid="j_forma-2018-0009_ref_010_w2aab3b7b1b1b6b1ab1ac10Aa">[10]</xref>, <xref ref-type="bibr" rid="j_forma-2018-0009_ref_005_w2aab3b7b1b1b6b1ab1ab5Aa">[5]</xref>, <xref ref-type="bibr" rid="j_forma-2018-0009_ref_009_w2aab3b7b1b1b6b1ab1ab9Aa">[9]</xref>) as well as in advanced ones (like <xref ref-type="bibr" rid="j_forma-2018-0009_ref_004_w2aab3b7b1b1b6b1ab1ab4Aa">[4]</xref>), after the initial definition of graphs the examples are usually given by graphical representations rather than explicit set theoretic descriptions, assuming a mutual understanding how the representation is to be translated into a description fitting the definition. However, Mizar <xref ref-type="bibr" rid="j_forma-2018-0009_ref_002_w2aab3b7b1b1b6b1ab1ab2Aa">[2]</xref>, <xref ref-type="bibr" rid="j_forma-2018-0009_ref_003_w2aab3b7b1b1b6b1ab1ab3Aa">[3]</xref> does not possess this innate ability of humans to translate pictures into graphs. Therefore, if one wants to create graphs in Mizar without directly providing a set theoretic description (i.e. using the <monospace>createGraph</monospace> functor), a rigorous approach to the constructing operations is required.In this paper supergraphs are defined as an inverse mode to subgraphs as given in <xref ref-type="bibr" rid="j_forma-2018-0009_ref_008_w2aab3b7b1b1b6b1ab1ab8Aa">[8]</xref>. The three graph construction operations are defined as modes extending <monospace>Supergraph</monospace> similar to how the various remove operations were introduced as submodes of <monospace>Subgraph</monospace> in <xref ref-type="bibr" rid="j_forma-2018-0009_ref_008_w2aab3b7b1b1b6b1ab1ab8Aa">[8]</xref>. Many theorems are proven that describe how graph properties are transferred to special supergraphs. In particular, to prove that disconnected graphs cannot become connected by adding an edge between two vertices that lie in the same component, the theory of replacing a part of a walk with another walk is introduced in the preliminaries.</abstract>

Drawing a finite graph is usually done by a finite sequence of the following three operations.1. Draw a vertex of the graph.2. Draw an edge between two vertices of the graph.3. Draw an edge starting from a vertex of the graph and immediately draw a vertex at the other end of it.By this procedure any finite graph can be constructed. This property of graphs is so obvious that the author of this article has yet to find a reference where it is mentioned explicitly. In introductionary books (like [10], [5], [9]) as well as in advanced ones (like [4]), after the initial definition of graphs the examples are usually given by graphical representations rather than explicit set theoretic descriptions, assuming a mutual understanding how the representation is to be translated into a description fitting the definition. However, Mizar [2], [3] does not possess this innate ability of humans to translate pictures into graphs. Therefore, if one wants to create graphs in Mizar without directly providing a set theoretic description (i.e. using the createGraph functor), a rigorous approach to the constructing operations is required.In this paper supergraphs are defined as an inverse mode to subgraphs as given in [8]. The three graph construction operations are defined as modes extending Supergraph similar to how the various remove operations were introduced as submodes of Subgraph in [8]. Many theorems are proven that describe how graph properties are transferred to special supergraphs. In particular, to prove that disconnected graphs cannot become connected by adding an edge between two vertices that lie in the same component, the theory of replacing a part of a walk with another walk is introduced in the preliminaries.

About Supergraphs. Part I

Formalized Mathematics

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"About Supergraphs. Part I"}

Drawing a finite graph is usually done by a finite sequence of the following three operations.1. Draw a vertex of the graph.2. Draw an edge between two...

About Supergraphs. Part I

Publicado en línea: 24 dic 2018

Páginas: 101 - 124

Aceptado: 29 jun 2018

DOI: https://doi.org/10.2478/forma-2018-0009

Palabras clave
supergraph, graph operations

© 2018 Sebastian Koch, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

About Supergraphs. Part I

Publicado en línea: 24 dic 2018

Páginas: 101 - 124

Aceptado: 29 jun 2018

DOI: https://doi.org/10.2478/forma-2018-0009

Palabras clavesupergraph, graph operations

© 2018 Sebastian Koch, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Palabras clave
supergraph, graph operations