This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations .(February 2014) (Learn how and when to remove this template message) |

In mathematics, and more specifically in graph theory, a **vertex** (plural **vertices**) or **node** is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

From the point of view of graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises; for instance, a semantic network is a graph in which the vertices represent concepts or classes of objects.

The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices. A vertex *w* is said to be adjacent to another vertex *v* if the graph contains an edge (*v*,*w*). The neighborhood of a vertex *v* is an induced subgraph of the graph, formed by all vertices adjacent to *v*.

The degree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An **isolated vertex** is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex).^{ [1] } A **leaf vertex** (also **pendant vertex**) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿^{ +}(v), from the indegree (number of incoming edges), denoted 𝛿^{−}(v); a **source vertex** is a vertex with indegree zero, while a **sink vertex** is a vertex with outdegree zero. A **simplicial vertex** is one whose neighbors form a clique: every two neighbors are adjacent. A universal vertex is a vertex that is adjacent to every other vertex in the graph.

A cut vertex is a vertex the removal of which would disconnect the remaining graph; a vertex separator is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A k-vertex-connected graph is a graph in which removing fewer than *k* vertices always leaves the remaining graph connected. An independent set is a set of vertices no two of which are adjacent, and a vertex cover is a set of vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.

A graph is vertex-transitive if it has symmetries that map any vertex to any other vertex. In the context of graph enumeration and graph isomorphism it is important to distinguish between **labeled vertices** and **unlabeled vertices**. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information.

Vertices in graphs are analogous to, but not the same as, vertices of polyhedra: the skeleton of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The vertex figure of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.

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* which are connected by *edges*. A distinction is made between **undirected graphs**, where edges link two vertices symmetrically, and **directed graphs**, where edges link two vertices asymmetrically; see Graph 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 graph theory, a **tree** is an undirected graph in which any two vertices are connected by *exactly one* path, or equivalently a connected acyclic undirected graph. A **forest** is an undirected graph in which any two vertices are connected by *at most one* path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

In mathematics, particularly graph theory, and computer science, a **directed acyclic graph** is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again. Equivalently, a DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence.

In the mathematical field of graph theory, a **bipartite graph** is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the *parts* of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

This is a **glossary of graph theory terms**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

In mathematics, and more specifically in graph theory, a **graph** is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called *vertices* and each of the related pairs of vertices is called an *edge*. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

In the mathematical discipline of graph theory, the **line graph** of an undirected graph *G* is another graph L(*G*) that represents the adjacencies between edges of *G*. L(*G*) is constructed in the following way: for each edge in *G*, make a vertex in L(*G*); for every two edges in *G* that have a vertex in common, make an edge between their corresponding vertices in L(*G*).

In computer science, a **topological sort** or **topological ordering** of a directed graph is a linear ordering of its vertices such that for every directed edge *uv* from vertex *u* to vertex *v*, *u* comes before *v* in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications especially in ranking problems such as feedback arc set.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0.

In graph theory, a part of discrete mathematics, the **BEST theorem** gives a product formula for the number of Eulerian circuits in directed (oriented) graphs. The name is an acronym of the names of people who discovered it: de **B**ruijn, van Aardenne-**E**hrenfest, **S**mith and **T**utte.

In mathematics and computer science, **connectivity** is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In the area of graph theory in mathematics, a **signed graph** is a graph in which each edge has a positive or negative sign.

In graph theory, a connected graph is ** k-edge-connected** if it remains connected whenever fewer than

In combinatorics, an area of mathematics, **graph enumeration** describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the graph. These problems may be solved either exactly or asymptotically. The pioneers in this area of mathematics were George Pólya, Arthur Cayley and J. Howard Redfield.

In graph theory, a **pseudoforest** is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A **pseudotree** is a connected pseudoforest.

In graph theory, a **Halin graph** is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In mathematics, and more specifically in graph theory, a **directed graph** is a graph that is made up of a set of vertices connected by edges, where the edges have a direction associated with them.

In graph theory, a branch of mathematics, the **Herschel graph** is a bipartite undirected graph with 11 vertices and 18 edges, the smallest non-Hamiltonian polyhedral graph. It is named after British astronomer Alexander Stewart Herschel.

In graph theory, a **caterpillar** or **caterpillar tree** is a tree in which all the vertices are within distance 1 of a central path.

In graph theory, a ** k-degenerate graph** is an undirected graph in which every subgraph has a vertex of degree at most

- ↑ File:Small Network.png; example image of a network with 8 vertices and 10 edges

- Gallo, Giorgio; Pallotino, Stefano (1988). "Shortest path algorithms".
*Annals of Operations Research*.**13**(1): 1–79. doi:10.1007/BF02288320. - Berge, Claude,
*Théorie des graphes et ses applications*. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001) - Chartrand, Gary (1985).
*Introductory graph theory*. New York: Dover. ISBN 0-486-24775-9. - Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986).
*Graph theory, 1736-1936*. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9. - Harary, Frank (1969).
*Graph theory*. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8. - Harary, Frank; Palmer, Edgar M. (1973).
*Graphical enumeration*. New York, Academic Press. ISBN 0-12-324245-2.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.