Volume 6, 1994

University of Bialystok

Copyright (c) 1994 Association of Mizar Users

**Yozo Toda**- Information Processing Center, Chiba University

- A graph is simple when \begin{itemize} \parskip -1mm \item it is non-directed, \item there is at most one edge between two vertices, \item there is no loop of length one. \end{itemize} A formalization of simple graphs is given from scratch. There is already an article [10], dealing with the similar subject. It is not used as a starting-point, because [10] formalizes directed non-empty graphs. Given a set of vertices, edge is defined as an (unordered) pair of different two vertices and graph as a pair of a set of vertices and a set of edges.\par The following concepts are introduced: \begin{itemize} \parskip -1mm \item simple graph structure, \item the set of all simple graphs, \item equality relation on graphs. \item the notion of degrees of vertices; the number of edges connected to, or the number of adjacent vertices, \item the notion of subgraphs, \item path, cycle, \item complete and bipartite complete graphs, \end{itemize}\par Theorems proved in this articles include: \begin{itemize} \parskip -1mm \item the set of simple graphs satisfies a certain minimality condition, \item equivalence between two notions of degrees. \end{itemize}

- Preliminaries
- Simple Graphs
- Equality Relation on Simple Graphs
- Properties of Simple Graphs
- Subgraphs
- Degree of Vertices
- Path and Cycle
- Some Famous Graphs

- [1]
Grzegorz Bancerek.
Cardinal numbers.
*Journal of Formalized Mathematics*, 1, 1989. - [2]
Grzegorz Bancerek.
The fundamental properties of natural numbers.
*Journal of Formalized Mathematics*, 1, 1989. - [3]
Grzegorz Bancerek and Krzysztof Hryniewiecki.
Segments of natural numbers and finite sequences.
*Journal of Formalized Mathematics*, 1, 1989. - [4]
Jozef Bialas.
Group and field definitions.
*Journal of Formalized Mathematics*, 1, 1989. - [5]
Czeslaw Bylinski.
Functions and their basic properties.
*Journal of Formalized Mathematics*, 1, 1989. - [6]
Czeslaw Bylinski.
Functions from a set to a set.
*Journal of Formalized Mathematics*, 1, 1989. - [7]
Czeslaw Bylinski.
Some basic properties of sets.
*Journal of Formalized Mathematics*, 1, 1989. - [8]
Czeslaw Bylinski.
Finite sequences and tuples of elements of a non-empty sets.
*Journal of Formalized Mathematics*, 2, 1990. - [9]
Agata Darmochwal.
Finite sets.
*Journal of Formalized Mathematics*, 1, 1989. - [10]
Krzysztof Hryniewiecki.
Graphs.
*Journal of Formalized Mathematics*, 2, 1990. - [11]
Andrzej Trybulec.
Semilattice operations on finite subsets.
*Journal of Formalized Mathematics*, 1, 1989. - [12]
Andrzej Trybulec.
Tarski Grothendieck set theory.
*Journal of Formalized Mathematics*, Axiomatics, 1989. - [13]
Andrzej Trybulec.
Subsets of real numbers.
*Journal of Formalized Mathematics*, Addenda, 2003. - [14]
Andrzej Trybulec and Agata Darmochwal.
Boolean domains.
*Journal of Formalized Mathematics*, 1, 1989. - [15]
Zinaida Trybulec.
Properties of subsets.
*Journal of Formalized Mathematics*, 1, 1989.

[ Download a postscript version, MML identifier index, Mizar home page]