Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph (discrete mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics. In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph (discrete mathematics) for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics. Refer to the glossary of graph theory for basic definitions in graph theory. Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. In one restricted but very common sense of the term, a graph is an ordered pair G = (V, E) comprising: To avoid ambiguity, this type of object may be called precisely an undirected simple graph. In the edge {x, y}, the vertices x and y are called the endpoints of the edge. The edge is said to join x and y and to be incident on x and on y. A vertex may exist in a graph and not belong to an edge. A loop is an edge that joins a vertex to itself. Multiple edges are two or more edges that join the same two vertices. In one more general sense of the term allowing multiple edges, a graph is an ordered triple G = (V, E, ϕ) comprising: To avoid ambiguity, this type of object may be called precisely an undirected multigraph. Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex x is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) {x, x} = {x} which is not in {{x, y} | (x, y) ∈ V2 ∧ x ≠ y}. So to allow loops the definitions must be expanded. For undirected simple graphs, E ⊆ {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} should become E ⊆ {{x, y} | (x, y) ∈ V2}. For undirected multigraphs, ϕ: E → {{x, y} | (x, y) ∈ V2 ∧ x ≠ y} should become ϕ: E → {{x, y} | (x, y) ∈ V2}. To avoid ambiguity, these types of objects may be called precisely an undirected simple graph permitting loops and an undirected multigraph permitting loops respectively.