Recently, I have started learning graph theory, here are a list of terminologies that are commonly used in graph theory,
A graph is a collection of vertices or nodes and of edges.
Two vertices are adjacent if there is an edge that has them as endpoints. An edge and a vertex are said to be incident if the vertex is an endpoint of the edge.
If is a subset of the vertices, then the induced subgraph is the graph obtained by deleting all vertices outside , keeping only edges with both endpoints in .
The complement of is a graph with the same vertex set as and .
A graph is bipartite if the vertex set can be partitioned into two non-empty disjoint sets such that edges only run between and or there are no edge that has both endpoints in the set.
A graph is complete bipartite if is bipartite and all possible edges between the two sets are drawn. In the case where such a graph is denoted by .
Let A graph is said to be -partite if the vertex set can be partitioned into pairwise disjoint sets such that no edge has both endpoints in the same set.
A complete k-partite graph is defined similarly as a complete bipartite. In the case where , such a graph is denoted by . (Note that a 2-partite graph is simply a bipartite graph.)
An edge whose endpoints are the same is called a loop.
A graph where there is more than one edge joining a pair of vertices is called a multigraph.
A graph without loops and is not a multigraph is said to be simple.
A graph is planar if it is possible to draw it in the plane without crossing any edges.
The chromatic number of a graph is the minimum number of colours needed to colour the vertices without having the same colour for any two adjacent vertices.
A clique or complete graph on vertices, denoted , is the -vertex graph with all possible edges.
A path is a sequence of distinct, pairwise-adjacent vertices. (A graph itself can also be called a path.) The length of a path is defined to be the number of edges in the path.
A walk is a sequence of not-necessarily-distinct, pairwise-adjacent vertices.
A cycle is a path for which the first and last vertices are adjacent. (A graph itself can also be called a cycle.) The length of a cycle is defined to be the number of vertices (or edges) in the path.
The degree of a vertex is the number of edges that are incident to .
The distance between two vertices in a graph is defined to be the length of the shortest path joining . (In the case the graph is disconnected, this may not be well-defined.)
A graph is connected if for any pair of vertices, there exists a path joining the two vertices. Otherwise, a graph is disconnected.
A tree is a connected graph with no cycles.
A forest is a not-necessarily-connected graph with no cycles.