Graph theory is a branch of mathematics that studies relationships between objects. These relationships can be represented using diagrams called graphs, making graph theory useful for understanding networks, connections, routes, and structures. A graph can represent anything from roads connecting cities and friendships between people to links between web pages or communication between computers.
To work with graphs effectively, it is important to understand their basic terminology and the counting formulas used to describe them. Terms such as vertex, edge, degree, path, cycle, connected graph, simple graph, and complete graph form the foundation of graph theory. Basic counting formulas then help determine the number of edges, degrees, paths, or other structural properties of a graph.
This article introduces the most important graph theory terms and explains the basic counting formulas in a simple way.
What Is a Graph in Graph Theory?
A graph is a mathematical structure consisting of objects called vertices and relationships between those objects called edges.
For example, suppose four cities are connected by roads. Each city can be represented by a vertex, while each road can be represented by an edge. The resulting diagram is a graph.
A graph is commonly written using the notation G = (V, E), where V represents the set of vertices and E represents the set of edges.
The vertices represent the objects being studied, while the edges represent relationships or connections between them.
Graphs can be used in many areas, including mathematics, computer science, transportation, communication networks, social networks, biology, and data science.
Vertex
A vertex is a basic object or point in a graph. Vertices are sometimes also called nodes.
For example, if a graph represents a network of computers, each computer can be represented by a vertex.
The set of all vertices in a graph is called the vertex set and is usually represented by V.
If a graph contains five vertices, we can write:
V = {A, B, C, D, E}
Here, A, B, C, D, and E are the vertices.
Edge
An edge represents a connection between two vertices.
For example, if A and B represent two computers and they are directly connected, the connection between them is an edge.
In an undirected graph, an edge connecting A and B is commonly written as AB or {A, B}.
The set of all edges is represented by E.
Therefore, a graph can be described by its vertex set and edge set.
Adjacent Vertices
Two vertices are called adjacent if an edge directly connects them.
For example, if an edge connects A and B, then A and B are adjacent.
Adjacency is useful when determining whether two objects have a direct relationship in a network.
Incident Edge
An edge is said to be incident to a vertex if the vertex is one of the endpoints of that edge.
For example, if edge AB connects vertices A and B, then AB is incident to both A and B.
The concepts of adjacency and incidence are closely related but describe different aspects of a graph.
Degree of a Vertex
The degree of a vertex is the number of edges connected to that vertex.
For example, if four edges meet at vertex A, then the degree of A is 4.
The degree of a vertex is commonly written as deg(v).
In a simple undirected graph, each edge connected to a vertex contributes one to its degree.
Basic Degree Formula
deg(v) = Number of edges incident to vertex v
A vertex with degree 0 is called an isolated vertex.
A vertex with degree 1 is called a pendant vertex or leaf in many graph-theory contexts.
Order and Size of a Graph
Two basic measurements are commonly used to describe the size of a graph.
The order of a graph is the number of vertices in the graph.
The size of a graph is the number of edges in the graph.
If a graph has 8 vertices and 12 edges, then its order is 8 and its size is 12.
Basic Notation
Order of graph = |V|
This notation is especially useful when discussing formulas involving the number of vertices and edges.
Simple Graph
A simple graph is an undirected graph that has no loops and no multiple edges between the same pair of vertices.
A loop is an edge that begins and ends at the same vertex.
Multiple edges occur when two vertices are connected by more than one edge.
Simple graphs are among the most commonly studied graph structures.
Multigraph
A multigraph is a graph that may contain multiple edges connecting the same pair of vertices.
For example, if two cities are connected by several different roads, those roads can be represented by multiple edges between the same pair of vertices.
Depending on the definition being used, loops may also be allowed in a multigraph.
Directed Graph
A directed graph, or digraph, is a graph in which edges have directions.
Instead of simply connecting A and B, a directed edge can point from A to B.
This can represent a one-way relationship, such as a one-way road, a social-media follow, or a link between web pages.
In directed graphs, the two main degree concepts are indegree and outdegree.
The indegree counts edges entering a vertex, while the outdegree counts edges leaving a vertex.
Directed Degree Formula
deg(v) = indeg(v) + outdeg(v)
Weighted Graph
A weighted graph is a graph in which numerical values are assigned to edges or, in some applications, vertices.
The values are called weights.
For example, a road network may assign distance to each road, while a computer network may assign communication cost or delay.
Weighted graphs are important in problems involving shortest routes, minimum costs, and optimization.
Complete Graph
A complete graph is a simple graph in which every pair of distinct vertices is connected by exactly one edge.
A complete graph with n vertices is written as Kₙ.
For example, K₃ contains three vertices, with every vertex connected to the other two.
The number of edges in a complete graph is given by the following formula.
Complete Graph Edge Formula
E = n(n − 1) / 2
where:
n = number of vertices
E = number of edges
For example, a complete graph with 5 vertices has:
E = 5(5 − 1) / 2
Therefore, K₅ has 10 edges.
Regular Graph
A graph is called regular if every vertex has the same degree.
If every vertex has degree r, the graph is called an r-regular graph.
For example, if every vertex in a graph has degree 3, the graph is 3-regular.
Regular graphs have an important relationship between the number of vertices, degree, and edges.
Edge Formula for a Regular Graph
2E = nr
Therefore:
E = nr / 2
where:
n = number of vertices
r = degree of every vertex
E = number of edges
Handshaking Lemma
One of the most important basic results in graph theory is the Handshaking Lemma.
It states that the sum of the degrees of all vertices in an undirected graph is twice the number of edges.
This happens because every edge has two endpoints and therefore contributes 2 to the total degree count.
Handshaking Formula
Σ deg(v) = 2E
where:
Σ deg(v) = sum of the degrees of all vertices
E = number of edges
For example, if the degrees of five vertices are 2, 3, 2, 4, and 1, their total degree is 12. Therefore, the graph contains:
E = 12 / 2
So the graph has 6 edges.
Odd-Degree Vertex Property
The Handshaking Lemma leads to an important result: the number of vertices with odd degree in an undirected graph is always even.
For example, a graph may have 2, 4, 6, or 8 odd-degree vertices, but it cannot have exactly 3 or 5 odd-degree vertices.
This property is useful for checking whether a proposed degree sequence can belong to an undirected graph.
Path
A path is a sequence of vertices connected by edges.
For example:
A → B → C → D
represents a path from A to D through B and C.
The length of a path is the number of edges it contains.
Therefore, the path A → B → C → D has length 3.
Walk
A walk is a sequence of vertices and edges in which consecutive vertices are connected.
Unlike a simple path, a walk may repeat vertices or edges.
For example:
A → B → C → B → D
is a walk because the vertex B is visited more than once.
Trail
A trail is a walk in which no edge is repeated.
Vertices may still be repeated in a trail.
This distinction is useful when studying routes through networks where using the same connection more than once is not allowed.
Cycle
A cycle is a closed path that starts and ends at the same vertex without repeating other vertices.
For example:
A → B → C → A
forms a cycle.
Cycles are important in network analysis because they represent closed routes or circular relationships.
Connected Graph
A graph is connected if there is a path between every pair of vertices.
In a connected graph, every vertex can be reached from every other vertex.
If some vertices cannot be reached from others, the graph is disconnected.
A disconnected graph consists of two or more connected components.
Subgraph
A subgraph is a graph formed from a subset of the vertices and edges of another graph.
For example, if a graph contains ten vertices, a smaller graph containing some of those vertices and their corresponding edges may form a subgraph.
Subgraphs are useful when studying smaller structures within a larger network.
Bipartite Graph
A bipartite graph is a graph whose vertices can be divided into two disjoint sets so that every edge connects a vertex from one set to a vertex from the other set.
There are no edges connecting two vertices within the same set.
Bipartite graphs are useful for representing relationships between two different categories of objects, such as students and courses or workers and jobs.
Complete Bipartite Graph
A complete bipartite graph connects every vertex in one set to every vertex in the other set.
It is commonly written as Kₘ,ₙ, where m and n represent the number of vertices in the two sets.
Complete Bipartite Edge Formula
E = mn
For example, K₂,₃ contains:
E = 2 × 3
Therefore, it has 6 edges.
Basic Counting Formulas in Graph Theory
Counting formulas allow us to determine important graph properties without drawing every connection individually.
Some of the most useful formulas are summarized below.
Number of Edges in a Complete Graph
E = n(n − 1) / 2
Handshaking Lemma
Σ deg(v) = 2E
Number of Edges in an r-Regular Graph
E = nr / 2
Number of Edges in a Complete Bipartite Graph
E = mn
Sum of Degrees in a Graph
Sum of degrees = 2 × Number of edges
Maximum Number of Edges in a Simple Undirected Graph
For a simple undirected graph with n vertices, the maximum possible number of edges occurs when every pair of vertices is connected.
Eₘₐₓ = n(n − 1) / 2
This is exactly the number of edges in the complete graph Kₙ.
Counting Possible Edges Between Vertices
A useful way to understand the complete-graph formula is through combinations.
Every edge in a simple undirected graph connects two different vertices. Therefore, the number of possible edges is the number of ways to choose 2 vertices from n vertices.
Combination Formula
C(n, 2) = n(n − 1) / 2
This explains why the maximum number of edges in a simple graph is:
Eₘₐₓ = C(n, 2)
For example, with 6 vertices:
Eₘₐₓ = 6(6 − 1) / 2
So a simple graph with 6 vertices can have at most 15 edges.
Counting Edges from Vertex Degrees
Sometimes the number of edges is not given directly, but the degree of every vertex is known.
In that situation, the Handshaking Lemma can be used.
Suppose a graph has degrees:
3, 2, 4, 3, 2
The sum is:
3 + 2 + 4 + 3 + 2 = 14
Using the Handshaking Lemma:
2E = 14
Therefore, the graph contains 7 edges.
Why Graph Theory Terminology Matters
Learning graph theory formulas without understanding the terminology can make problems unnecessarily difficult. Terms such as vertex, edge, degree, path, cycle, connected graph, and complete graph describe the structures that the formulas operate on.
For example, the formula for a complete graph is useful only when you recognize that every pair of vertices is connected. Similarly, the Handshaking Lemma becomes easy to apply once you understand that every edge contributes two to the total degree.
A strong foundation in terminology therefore makes later topics such as Euler paths, Hamiltonian paths, trees, planar graphs, graph coloring, shortest-path algorithms, and network optimization much easier to understand.
Conclusion
Graph theory provides a mathematical language for studying connections and relationships. Its basic concepts begin with vertices and edges, while more advanced structures include paths, cycles, connected graphs, complete graphs, bipartite graphs, and weighted graphs.
Basic counting formulas provide efficient ways to determine the number of edges and other properties of a graph. The Handshaking Lemma, the complete graph formula, the regular graph formula, and the complete bipartite graph formula are especially important foundations.
Once these terms and formulas become familiar, graph theory becomes much easier to approach. They provide the foundation for solving more advanced problems in discrete mathematics, computer science, algorithms, network analysis, and many real-world systems involving connections.
FAQs
1. What is graph theory?
Graph theory is a branch of mathematics that studies objects and the relationships or connections between them. These objects are represented by vertices, while their connections are represented by edges. A graph can be used to represent many real-world systems, such as road networks, computer networks, social relationships, and communication systems. Graph theory also provides methods for analyzing paths, cycles, connections, and networks. Basic concepts such as vertices, edges, degree, paths, cycles, and connected graphs form its foundation. Learning these terms first makes it easier to understand more advanced topics such as trees, graph coloring, network optimization, and graph algorithms.
2. What is a vertex in graph theory?
A vertex is a fundamental point or object in a graph. Vertices are also commonly called nodes. They represent the objects or entities being studied in a particular network. For example, in a road network, cities can be represented by vertices, while roads are represented by edges. In a social network, people can be represented by vertices and relationships by edges. A graph may contain any number of vertices depending on the problem. The complete collection of vertices is called the vertex set, usually represented by V. Understanding vertices is essential because edges connect vertices and most graph properties are based on their relationships.
3. What is an edge in graph theory?
An edge is a connection between two vertices in a graph. It represents a relationship, link, or interaction between the objects represented by those vertices. For example, if two cities are connected by a road, the cities can be represented by vertices and the road by an edge. In an undirected graph, an edge does not have a direction, while in a directed graph, an edge points from one vertex to another. Edges form the basic connections within a graph. The collection of all edges is called the edge set, usually represented by E. The number of edges is called the size of the graph.
4. What is the degree of a vertex?
The degree of a vertex is the number of edges incident to that vertex. In a simple undirected graph, it tells us how many direct connections a vertex has. For example, if four edges meet at vertex A, then the degree of A is 4. A vertex with degree 0 is called an isolated vertex, while a vertex with degree 1 is commonly called a pendant vertex or leaf. Degree is an important graph property because it helps describe the structure and connectivity of a graph. The sum of the degrees of all vertices is also related to the number of edges through the Handshaking Lemma.
5. What is the Handshaking Lemma?
The Handshaking Lemma is a fundamental result in graph theory. It states that the sum of the degrees of all vertices in an undirected graph is equal to twice the number of edges. The reason is simple: every edge has two endpoints, so every edge contributes two to the total degree count. The formula is Σ deg(v) = 2E, where E represents the number of edges. For example, if the total degree of all vertices is 20, the graph has 10 edges. The lemma is useful for finding the number of edges when vertex degrees are known and for checking whether a degree sequence is possible.
6. What is a complete graph?
A complete graph is a simple graph in which every pair of distinct vertices is connected by exactly one edge. A complete graph with n vertices is commonly represented by Kₙ. Because every possible pair of vertices is connected, complete graphs contain the maximum possible number of edges for a simple undirected graph with the same number of vertices. The number of edges is calculated using E = n(n − 1) / 2. For example, a complete graph with 5 vertices has 10 edges. Complete graphs are important in graph theory because they provide a useful model for studying maximum connectivity and many counting problems.
7. How do you calculate the number of edges in a complete graph?
The number of edges in a complete graph with n vertices can be calculated using the formula E = n(n − 1) / 2. This works because every edge connects a unique pair of vertices, and the formula counts all possible pairs. For example, if a complete graph has 6 vertices, substitute n = 6 into the formula: E = 6(6 − 1) / 2 = 15. Therefore, the graph contains 15 edges. This formula is also the maximum number of edges possible in a simple undirected graph containing n vertices. It is one of the most important basic counting formulas in graph theory.
8. What is a bipartite graph?
A bipartite graph is a graph whose vertices can be divided into two separate sets so that every edge connects a vertex from one set to a vertex from the other set. There are no edges connecting two vertices within the same set. For example, students can form one set and courses another, with an edge representing enrollment. A complete bipartite graph connects every vertex in the first set to every vertex in the second set. If the two sets contain m and n vertices, respectively, the number of edges is E = mn. Bipartite graphs are widely used for matching and relationship problems.
9. What is the difference between a path, walk, and cycle?
A walk is a sequence of vertices connected by edges where vertices or edges may be repeated. A trail is a walk in which no edge is repeated. A path generally does not repeat vertices, making it more restrictive than a walk. A cycle is a closed path that starts and ends at the same vertex without repeating the other vertices. For example, A → B → C → A forms a cycle. These concepts are important for analyzing routes and connections in graphs. Understanding their differences helps when studying Euler paths, Hamiltonian paths, network routes, and graph algorithms.
10. Why are graph theory counting formulas important?
Graph theory counting formulas provide efficient ways to determine important properties of graphs without having to draw or inspect every connection individually. For example, the complete graph formula E = n(n − 1) / 2 determines the maximum number of edges in a simple graph with n vertices. The Handshaking Lemma, Σ deg(v) = 2E, determines the number of edges from the degrees of the vertices. The complete bipartite graph formula E = mn counts connections between two vertex sets. These formulas are useful in discrete mathematics, computer science, network analysis, algorithms, communication systems, and many other applications.
