Metamath Proof Explorer

Table of Contents - 16. GRAPH THEORY

To give an overview of the definitions and terms used in the context of graph theory, a glossary is provided in the following, mainly according to definitions in [Bollobas] p. 1-8 or in [Diestel] p. 2-28. Although this glossary concentrates on undirected graphs, many of the concepts are also useful for directed graphs. <h1>Basic concepts:</h1> <table border="1" id="graph-theory-glossary0"> <tr><th>Term</th><th>Reference</th><th>Definition</th><th>Remarks</th></tr> <tr><td>Vertex</td><td> df-vtx </td> <td>A vertex of a graph is an element of the set of vertices of the graph .</td> <td>The set of vertices (corresponding to V(G) in [Bollobas] p. 1) is usually the first component of the graph if it is represented by an ordered pair (see opvtxfv), or the base set of the graph if it is represented as extensible structure (see basvtxval).</td></tr> <tr><td>Edge</td><td> df-edg </td> <td>An edge of a graph is a nonempty set of vertices of the graph. It is said that these vertices are "joined" or "connected" by the edge, see [Bollobas] p. 1.</td> <td>The set of edges (corresponding to E(G) in [Bollobas] p. 1) is usually the range of the second component of the graph if it is represented by an ordered pair , or the range of the component of the graph if it is represented as extensible structure. </td></tr> <tr><td>Loop</td><td></td> <td>A loop in a graph is an edge which connects a single vertex with itself (or, according to [Bollobas] p. 7 "joins a vertex to itself").</td> <td>In other words, a loop is an edge which is a singleton consisting of a vertex : </td></tr> <tr><td>Edge function resp. indexed edges</td> <td> df-iedg </td> <td>An edge function (or indexed set of edges) of a graph is a mapping of an arbitrary index set to nonempty sets of vertices of the graph.</td> <td>The edge function is usually the second component of the graph if it is represented by an ordered pair (see opiedgfv), or the component of the graph if it is represented as extensible structure (see edgfiedgval). The set of edges of a graph is the range of its edge function: , see edgval. Whereas the concept of plain edges is sufficient for simple hypergraphs, indexed edges are required for e.g. multigraphs in which the same vertices may be connected by more than one edge.</td></tr> </table> <h1>Basic kinds of graphs:</h1> <table border="1" id="graph-theory-glossary1"> <tr><th>Term</th><th>Reference</th><th>Definition</th><th>Remarks</th></tr> <tr><td>Undirected hypergraph</td><td> df-uhgr </td> <td>a class with an edge function which is a function into the power set of the vertices : .</td> <td>In this most general definition of a graph, an "edge" may connect three or more vertices with each other, see [Berge] p. 1. In Wikipedia "Hypergraph", see https://en.wikipedia.org/wiki/Hypergraph (18-Jan-2020) such a hypergraph is called a "non-simple hypergraph", "multiple hypergraph" or "multi-hypergraphs". According to Wikipedia "Incidence structure", see https://en.wikipedia.org/wiki/Incidence_structure (18-Jan-2020) "Each hypergraph [...] can be regarded as an incidence structure in which the [vertices] play the role of "points", the corresponding family of [edges] plays the role of "lines" and the incidence relation is set membership". Notice that by using the (possibly more than one) edges connecting the same vertices could not be distinguished anymore. Therefore, this representation will only be used for undirected simple hypergraphs.</td></tr> <tr><td>Undirected simple hypergraph</td><td> df-ushgr </td> <td>a class with an edge function which is a one-to-one function into the power set of the vertices : .</td> <td>See also Wikipedia "Hypergraph", https://en.wikipedia.org/wiki/Hypergraph (18-Jan-2020). This is how a "hypergraph" is defined in Section I.1 in [Bollobas] p. 7 or the definition in section 1.10 in [Diestel] p. 27. A simple hypergraph has at most one edge between the same vertices, hence a pseudograph needs not be a simple hypergraph. According to [Berge] p. 1, "A simple hypergraph (or "Sperner family") is a hypergraph H = { E_1, E_2, ..., E_m } such that E_i C_ E_j => i = j". By this definition, a simple hypergraph cannot contain the edges E_1 = { v_1 , v_2 } and E_2 = { v_1, v_2, v_3 }, because E_1 C_ E_2, but 1 =/= 2. </td></tr> <tr><td>Undirected loop-free hypergraph</td><td>---</td> <td>an undirected hypergraph without a loop, i.e. all edges connect at least two vertices.</td> <td></td></tr> <tr><td>Undirected pseudograph</td><td> df-upgr </td> <td>a class with an edge function which is a function into the set of (proper or not proper) unordered pairs of vertices .</td> <td>A proper unordered pair contains two different elements, a not proper unordered pair contains two times the same element, so it is a singleton (see preqsn). This means a pseudograph may contain loops. This definition corresponds to the definition of a "multigraph" in Section I.1 in [Bollobas] p. 7, "In a multigraph both multiple edges [joining two vertices] and multiple loops [joining a vertex to itself] are allowed", or in [Diestel] p. 28, "A multigraph is a pair (V,E) of disjoint sets (of vertices and edges) together with a map E -> V u. [V]^2 assigning to every edge either one or two vertices, its end(s).".</td></tr> <tr><td>Undirected multigraph</td><td> df-umgr </td> <td>a class with an edge function which is a function into the set of (proper!) unordered pairs of vertices .</td> <td>This definition is according to Chartrand, Gary and Zhang, Ping (2012): "A First Course in Graph Theory.", Dover, ISBN 978-0-486-48368-9, section 1.4, p. 26: "A multigraph M consists of a finite nonempty set V of vertices and a set E of edges, where every two vertices of M are joined by a finite number of edges (possibly zero). If two or more edges join the same pair of (distinct) vertices, then these edges are called parallel edges." A proper unordered pair contains two different elements, therefore a multigraph does not have loops.</td></tr> <tr><td>Undirected simple pseudograph</td><td> df-uspgr </td> <td>a class with an edge function which is a one-to-one function into the set of (proper or not proper) unordered pairs of vertices .</td> <td>This means that there is at most one edge between two vertices, and at most one loop from a vertex to itself.</td></tr> <tr><td>Undirected simple graph</td><td> df-usgr </td> <td>a class with an edge function which is a one-to-one function into the set of (proper!) unordered pairs of vertices .</td> <td>An ordered pair of two distinct sets (the vertices) and (the edges), the "usual" definition of a "graph", see, for example, the definition in section I.1 of [Bollobas] p. 1 or in section 1.1 of [Diestel] p. 2, can be identified with an undirected simple graph without loops by "indexing" the edges with themselves, see usgrausgrb. </td></tr> <tr><td>Finite graph</td><td> df-fusgr </td> <td>a graph with a finite set of vertices .</td> <td>See definitions in [Bollobas] p. 1 or [Diestel] p. 2. In simple graphs, the set of (indexed) edges (and therefore also the set of edges ) is finite if is finite, see fusgrfis. The number of edges is limited by (or " choose 2") with , see fusgrmaxsize. Analogously, the number of edges of an undirected simple pseudograph (which may have loops) is limited by . In pseudographs or multigraphs, however, can be infinite although is finite. </td></tr> <tr><td>Graph of finite size</td><td>---</td> <td>a graph with a finite set , i.e. with a finite number of edges.</td> <td>A graph can be of finite size although its set of vertices is infinite (most of the vertices would not be connected by an edge).</td></tr> </table> <h1>Terms and properties of graphs:</h1> <table border="1" id="graph-theory-glossary2"> <tr><th>Term</th><th>Reference</th><th>Definition</th><th>Remarks</th></tr> <tr><td>Edge joining resp. connecting (two) vertices</td> <td>---</td> <td>An edge joins resp. connects the vertices v_1, v_2, ... v_n () if = { v_1, v_2, ... v_n }.</td> <td>If , = { v_1 } is a loop, if , = { v_1 , v_2 } is an edge as it is usually defined, see definition in Section I.1 in [Bollobas] p. 1.</td></tr> <tr><td>(Two) Endvertices of an edge</td> <td> see definition in Section I.1 in [Bollobas] p. 1.</td> <td>If an edge joins the vertices v_1, v_2, ... v_n (), then the vertices v_1, v_2, ... v_n are called the endvertices of the edge .</td><td></td></tr> <tr><td>(Two) Adjacent vertices</td> <td> see definition in Section I.1 in [Bollobas] p. 1/2.</td> <td>The vertices v_1, v_2, ... v_n () are adjacent if there is an edge e = { v_1, v_2, ... v_n } joining these vertices. In this case, the vertices are incident with the edge e (see definition in Section I.1 in [Bollobas] p. 2) or connected by the edge e.</td> <td></td></tr> <tr><td>Edge ending at a vertex</td><td> </td> <td> An edge is ending at a vertex if the vertex is an endvertex of the edge: . In other words, the vertex is incident with the edge . </td><td></td></tr> <tr><td>(Two) Adjacent edges</td><td></td> <td>The edges e_0, e_1, ... e_n () are adjacent if they have exactly one common endvertex.</td> <td>Generalization of definition in Section I.1 in [Bollobas] p. 2.</td> </tr> <tr><td>Order of a graph</td> <td>see definition in Section I.1 in [Bollobas] p. 3</td> <td>The order of a graph is the number of vertices in the graph: .</td><td></td></tr> <tr><td>Size of a graph</td> <td>see definition in Section I.1 in [Bollobas] p. 3</td> <td>The size of a graph is the number of edges in the graph: . Or, for a simple graph : ).</td><td></td></tr> <tr><td>Neighborhood of a vertex</td> <td> df-nbgr resp. definition in Section I.1 in [Bollobas] p. 3</td> <td>A vertex connected with a vertex by an edge is called a neighbor of the vertex . The set of neighbors of a vertex is called the neighborhood (or open neighborhood) of the vertex . The closed neighborhood is the union of the (open) neighborhood of the vertex with .</td><td></td></tr> <tr><td>Degree of a vertex</td><td> df-vtxdg </td> <td>The degree of a vertex is the number of the edges ending at this vertex.</td> <td>In a simple graph, the degree of a vertex is the number of neighbors of this vertex, see definition in Section I.1 in [Bollobas] p. 3</td></tr> <tr><td>Isolated vertex</td><td> usgrvd0nedg </td> <td>A vertex is called isolated if it is not an endvertex of any edge, thus having degree 0.</td><td></td></tr> <tr><td>Universal vertex</td><td> df-uvtx </td> <td>A vertex is called universal if it is connected with every other vertex of the graph by an edge, thus having degree .</td><td></td></tr> </table> <h1>Special kinds of graphs:</h1> <table border="1" id="graph-theory-glossary3"> <tr><th>Term</th><th>Reference</th><th>Definition</th><th>Remarks</th></tr> <tr><td>Complete graph</td><td> df-cplgr </td> <td>A graph is called complete if each pair of vertices is connected by an edge.</td> <td>The size of a complete undirected simple graph of order is (or " choose 2"), see cusgrsize.</td></tr> <tr><td>Empty graph</td><td> uhgr0e </td> <td>A graph is called empty if it has no edges.</td> <td></td></tr> <tr><td>Null graph</td><td> uhgr0 and uhgr0vb </td> <td>A graph is called a null graph if it has no vertices (and therefore also no edges).</td><td></td></tr> <tr><td>Trivial graph</td><td> usgr1v </td> <td>A graph is called the "trivial graph" if it has only one vertex and no edges.</td><td></td></tr> <tr><td>Connected graph</td> <td> df-conngr resp. definition in Section I.1 in [Bollobas] p. 6</td> <td>A graph is called connected if for each pair of vertices there is a path between these vertices.</td><td></td></tr> </table> For the terms "Path", "Walk", "Trail", "Circuit", "Cycle" see the remarks below and the definitions in Section I.1 in [Bollobas] p. 4-5.