Editing Graph theory (section)

=== 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>.