Editing Graph theory (section)

== Definitions ==
{{further|Glossary of graph theory}}
Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related [[mathematical structure]]s.

=== Graph ===
[[File:Example of simple undirected graph.svg|150 px|thumb|An undirected graph with three vertices and three edges.]]

In one restricted but very common sense of the term,{{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref> a '''graph''' is an [[ordered pair]] <math>G=(V,E)</math> comprising:
* <math>V</math>, a [[Set (mathematics)|set]] of '''vertices''' (also called '''nodes''' or '''points''');
* <math>E \subseteq \{ \{x, y\} \mid x, y \in V \;\textrm{ and }\; x \neq y \}</math>, a [[Set (mathematics)|set]] of '''edges''' (also called '''links''' or '''lines'''), which are [[unordered pair]]s of vertices (that is, an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called an '''undirected simple graph'''.

In the edge <math>\{x, y\}</math>, the vertices <math>x</math> and <math>y</math> are called the '''endpoints''' of the edge. The edge is said to '''join''' <math>x</math> and <math>y</math> and to be '''incident''' on <math>x</math> and on <math>y</math>. A vertex may exist in a graph and not belong to an edge. Under this definition, '''[[multiple edges]]''', in which two or more edges connect the same vertices, are not allowed.
[[File:Example of simple undirected graph with loops.svg|150px|thumb|Example of an undirected multigraph with 3 vertices, 3 edges and 4 loops.]]
{{Multiple image
 | image1 = Example of simple undirected graph 2.svg
 | width1 = 75
 | caption1 =For vertices A,B,C and D, the degrees are respectively 4,4,5,1
 | image2 = Example of simple undirected graph 1.svg
 | width2 = 75
 | caption2 = For vertices U,V,W and X, the degrees are 2,2,3 and 1 respectively.
 | footer = Examples of finding the degree of vertices.
}}
In one more general sense of the term allowing multiple edges,{{sfn|Bender|Williamson|2010|p=149}}<ref>See, for instance, Graham et al., p. 5.</ref> a '''graph''' is an ordered triple <math>G=(V,E,\phi)</math> comprising:
* <math>V</math>, a [[Set (mathematics)|set]] of '''vertices''' (also called '''nodes''' or '''points''');
* <math>E</math>, a [[Set (mathematics)|set]] of '''edges''' (also called '''links''' or '''lines''');
* <math>\phi : E \to \{ \{x, y\} \mid x, y \in V \;\textrm{ and }\; x \neq y \}</math>, an '''incidence function''' mapping every edge to an [[unordered pair]] of vertices (that is, an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called an '''undirected [[multigraph]]'''.

A '''[[Loop (graph theory)|loop]]''' is an edge that joins a vertex to itself. Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex <math>x</math> to itself is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) <math>\{x, x\} = \{x\}</math> which is not in <math>\{ \{x, y\} \mid x, y \in V \;\textrm{ and }\; x \neq y \}</math>. To allow loops, the definitions must be expanded. For undirected simple graphs, the definition of <math>E</math> should be modified to <math>E \subseteq \{ \{x, y\} \mid x, y \in V \}</math>. For undirected multigraphs, the definition of <math>\phi</math> should be modified to <math>\phi : E \to \{ \{x, y\} \mid x, y \in V \}</math>. To avoid ambiguity, these types of objects may be called '''undirected simple graph permitting loops''' and '''undirected multigraph permitting loops''' (sometimes also '''undirected [[pseudograph]]'''), respectively.

<math>V</math> and <math>E</math> 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 graph|infinite case]]. Moreover, <math>V</math> is often assumed to be non-empty, but <math>E</math> is allowed to be the empty set. The '''order''' of a graph is <math>|V|</math>, its number of vertices. The '''size''' of a graph is <math>|E|</math>, its number of edges. The '''degree''' or '''valency''' of a vertex is the number of edges that are incident to it, where a loop is counted twice. The '''degree''' of a graph is the maximum of the degrees of its vertices.

In an undirected simple graph of order ''n'', the maximum degree of each vertex is {{nowrap|''n'' − 1}} and the maximum size of the graph is {{sfrac|''n''(''n'' − 1)|2}}.

The edges of an undirected simple graph permitting loops <math>G</math> induce a symmetric [[Binary relation#Homogeneous relation|homogeneous relation]] <math>\sim</math> on the vertices of <math>G</math> that is called the '''adjacency relation''' of <math>G</math>. Specifically, for each edge <math>(x,y)</math>, its endpoints <math>x</math> and <math>y</math> are said to be '''adjacent''' to one another, which is denoted <math>x \sim y</math>.

=== Directed graph ===
{{main|Directed graph}}
[[File:Example of simple directed graph.svg|thumb|150px|A directed graph with three vertices and four directed edges (the double arrow represents an edge in each direction).]]

A '''directed graph''' or '''digraph''' is a graph in which edges have orientations.

In one restricted but very common sense of the term,{{sfn|Bender|Williamson|2010|p=161}} a '''directed graph''' is an ordered pair <math>G=(V,E)</math> comprising:
* <math>V</math>, a [[Set (mathematics)|set]] of ''vertices'' (also called ''nodes'' or ''points'');
* <math>E \subseteq \left\{(x,y) \mid (x, y) \in V^2 \;\textrm{ and }\; x \neq y \right\}</math>, a [[Set (mathematics)|set]] of ''edges'' (also called ''directed edges'', ''directed links'', ''directed lines'', ''arrows'' or ''arcs'') which are [[ordered pair]]s of vertices (that is, an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called a '''directed simple graph'''. In set theory and graph theory, <math>V^n</math> denotes the set of {{mvar|n}}-[[tuple]]s of elements of <math>V,</math> that is, ordered sequences of <math>n</math> elements that are not necessarily distinct.

In the edge <math>(x, y)</math> directed from <math>x</math> to <math>y</math>, the vertices <math>x</math> and <math>y</math> are called the ''endpoints'' of the edge, <math>x</math> the ''tail'' of the edge and <math>y</math> the ''head'' of the edge. The edge is said to ''join'' <math>x</math> and <math>y</math> and to be ''incident'' on <math>x</math> and on <math>y</math>. A vertex may exist in a graph and not belong to an edge. The edge <math>(y,x)</math> is called the ''inverted edge'' of <math>(x, y)</math>. ''[[Multiple edges]]'', not allowed under the definition above, are two or more edges with both the same tail and the same head.

In one more general sense of the term allowing multiple edges,{{sfn|Bender|Williamson|2010|p=161}} a '''directed graph''' is an ordered triple <math>G=(V,E,\phi)</math> comprising:
* <math>V</math>, a [[Set (mathematics)|set]] of ''vertices'' (also called ''nodes'' or ''points'');
* <math>E</math>, a [[Set (mathematics)|set]] of ''edges'' (also called ''directed edges'', ''directed links'', ''directed lines'', ''arrows'' or ''arcs'');
* <math>\phi : E \to \left\{(x,y) \mid (x, y) \in V^2 \;\textrm{ and }\; x \neq y \right\}</math>, an ''incidence function'' mapping every edge to an [[ordered pair]] of vertices (that is, an edge is associated with two distinct vertices).

To avoid ambiguity, this type of object may be called a '''directed multigraph'''.

A ''[[Loop (graph theory)|loop]]'' is an edge that joins a vertex to itself. Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex <math>x</math> to itself is the edge (for a directed simple graph) or is incident on (for a directed multigraph) <math>(x,x)</math> which is not in <math>\left\{(x, y) \mid (x, y) \in V^2 \;\textrm{ and }\; x \neq y \right\}</math>. So to allow loops the definitions must be expanded. For directed simple graphs, the definition of <math>E</math> should be modified to <math>E \subseteq \left\{(x, y) \mid (x, y) \in V^2\right\}</math>. For directed multigraphs, the definition of <math>\phi</math> should be modified to <math>\phi : E \to \left\{(x, y) \mid (x, y) \in V^2\right\}</math>. To avoid ambiguity, these types of objects may be called precisely a '''directed simple graph permitting loops''' and a '''directed multigraph permitting loops''' (or a ''[[Quiver (mathematics)|quiver]]'') respectively.

The edges of a directed simple graph permitting loops <math>G</math> is a [[Binary relation#Homogeneous relation|homogeneous relation]] ~ on the vertices of <math>G</math> that is called the ''adjacency relation'' of <math>G</math>. Specifically, for each edge <math>(x,y)</math>, its endpoints <math>x</math> and <math>y</math> are said to be ''adjacent'' to one another, which is denoted <math>x</math> ~ <math>y</math>.