Graph Terminology in Discrete Mathematics

students, welcome to one of the most important starter ideas in graph theory 📘. Graphs are everywhere in real life: social networks, road maps, airline routes, computer connections, and even task dependencies in a project. In this lesson, you will learn the language of graphs so that you can read, describe, and solve problems using graph-theory ideas with confidence.

What Is a Graph?

In discrete mathematics, a graph is a mathematical model made of two parts: vertices and edges. A vertex is a point or node, and an edge is a connection between two vertices. We usually write a graph as $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges.

For example, if $V = \{A, B, C\}$ and $E = \{\{A,B\}, \{B,C\}\}$, then the graph has three vertices and two edges. The edge $\{A,B\}$ means that $A$ and $B$ are connected.

Graph terminology matters because it gives you a precise way to describe relationships. If a city map shows intersections as vertices and roads as edges, then graph theory can help answer questions like, “Can I get from one place to another?” or “Which route uses the fewest connections?” 🚗

A graph can be drawn in many different ways, but the underlying structure is what matters. Two drawings may look different and still represent the same graph if they have the same vertices and edges.

Vertices, Edges, and Special Types of Graphs

The vertices of a graph are the objects being studied, and the edges show how those objects are related. In a friendship graph, vertices could be people and edges could represent friendships. In a computer network, vertices could be devices and edges could represent cables or wireless links.

There are several common types of graphs you should know:

A simple graph 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 are more than one edge connecting the same two vertices.
A multigraph may allow multiple edges.
A pseudograph may allow loops and multiple edges.

Here is an example of a loop: if a vertex $A$ has an edge from $A$ back to $A$, then that edge is a loop. Loops are often useful in applications, but they are not allowed in a simple graph.

Understanding these terms helps students describe graphs correctly. For instance, if a network diagram contains repeated connections between the same pair of routers, that would not be a simple graph.

Directed and Undirected Graphs

Not all connections work the same way. In an undirected graph, edges have no direction. If $A$ is connected to $B$, then $B$ is connected to $A$ in the same way. This is often written using an unordered pair, such as $\{A,B\}$.

In a directed graph, also called a digraph, edges have direction. A directed edge from $A$ to $B$ is written as $(A,B)$ or $A \to B$. This means the connection goes one way. For example, a one-way street can be modeled with a directed edge because travel is allowed in one direction but not the other.

This difference is very important. If a website links from page $A$ to page $B$, that does not necessarily mean page $B$ links back to page $A$. A directed graph captures that one-way relationship.

When studying a graph, always ask whether the edges represent two-way or one-way connections. That question changes how you interpret paths, degrees, and reachability.

Adjacent Vertices, Incident Edges, and Neighborhoods

Two vertices are adjacent if they are connected by an edge. If $A$ and $B$ share an edge, then $A$ is adjacent to $B$ and $B$ is adjacent to $A$ in an undirected graph.

An edge is incident to the vertices it touches. So if edge $e$ connects $A$ and $B$, then $e$ is incident to both $A$ and $B$.

The neighborhood of a vertex is the set of vertices adjacent to it. For a vertex $v$, this is often written as $N(v)$.

Example: suppose a graph has vertices $\{A,B,C,D\}$ and edges $\{\{A,B\}, \{A,C\}, \{C,D\}\}$. Then:

$A$ is adjacent to $B$ and $C$.
$B$ is adjacent to $A$.
$C$ is adjacent to $A$ and $D$.
$N(A) = \{B,C\}$.

These ideas are useful because many graph problems are really questions about local connections. For example, in a social network, the neighborhood of a person is the set of direct friends.

Degree of a Vertex

The degree of a vertex is the number of edges incident to it. The degree of a vertex $v$ is written as $\deg(v)$.

In a simple undirected graph, if a vertex has three edges touching it, then its degree is $3$. If a vertex has no edges, its degree is $0$ and it is called an isolated vertex.

A vertex of degree $1$ is called a pendant vertex or leaf. This often appears at the “ends” of a graph.

For directed graphs, we use two kinds of degree:

In-degree, the number of edges entering a vertex
Out-degree, the number of edges leaving a vertex

Example: if $A \to B$ and $C \to B$, then vertex $B$ has in-degree $2$. If $B \to D$, then $B$ has out-degree $1$.

A key fact for undirected graphs is that the sum of all vertex degrees equals twice the number of edges:

$$\sum_{v \in V} \deg(v) = 2|E|.$$

This works because each edge contributes $1$ to the degree of each of its two endpoints. This idea is very useful for checking whether a proposed graph is possible. If the degree sum is odd, something is wrong, because the left side must be even.

Paths, Walks, and Cycles

A walk is a sequence of vertices where each consecutive pair is connected by an edge. Vertices and edges may repeat in a walk.

A path is a walk with no repeated vertices. Paths help describe how to move through a graph without looping back to the same place.

The length of a walk or path is the number of edges used.

Example: in a graph with edges $\{\{A,B\}, \{B,C\}, \{C,D\}\}$, the sequence $A, B, C, D$ is a path of length $3$.

A cycle is a path that starts and ends at the same vertex, with no other repeated vertices. Cycles show a closed route. For example, if $A, B, C, A$ uses edges $\{\{A,B\}, \{B,C\}, \{C,A\}\}$, then this is a cycle of length $3$.

Cycles matter in applications like scheduling and routing. A cycle in a dependency graph may show a problem, because one task may eventually depend on itself indirectly.

A graph with no cycles is called acyclic. If a graph is both connected and acyclic, it is a tree. Trees are central in discrete mathematics and computer science, but the idea begins with these basic graph terms.

Connectedness and Components

A graph is connected if there is a path between every pair of vertices. This means you can get from any vertex to any other vertex by moving along edges.

If a graph is not connected, it breaks into smaller parts called connected components. A connected component is a maximal connected subgraph. “Maximal” means you cannot add another vertex from the graph without losing connectedness.

Example: suppose a graph has one triangle made of $A$, $B$, and $C$, and another separate edge connecting $D$ and $E$. Then the graph has two connected components: one on $\{A,B,C\}$ and one on $\{D,E\}$.

This idea is useful in real life. A power grid with disconnected components may leave some areas without electricity. A social network with multiple components means some people are not connected through friendships at all.

Why Graph Terminology Matters for Midterm 1

Graph terminology is not just vocabulary; it is the foundation for solving problems in Intro to Graph Theory and later topics in Discrete Mathematics. On Midterm 1, you may be asked to identify graph parts, classify graphs, compute degrees, determine whether a walk is a path or a cycle, or decide whether a graph is connected.

A good strategy is to read graph questions carefully and translate the words into precise definitions. For example:

“Direct connection” may mean adjacent vertices.
“Number of links touching a vertex” means degree.
“A route that returns to the start” may mean a cycle.
“Can reach every vertex from every other vertex” means connected.

When students uses correct terminology, it becomes much easier to explain answers clearly and avoid mistakes. Graph theory works because definitions are exact, and exact language leads to exact reasoning ✅.

Conclusion

Graph terminology gives you the tools to describe relationships in a structured way. Vertices, edges, adjacency, degree, paths, cycles, and connectedness are the building blocks of graph theory. These ideas appear in many practical settings, from road systems to computer networks to social media. By mastering this language, students builds a strong base for Midterm 1 and for the rest of Intro to Graph Theory. The more clearly you can name graph features, the more successfully you can analyze and solve graph problems.

Study Notes

A graph is written as $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges.
A vertex is a point or node; an edge is a connection between two vertices.
A simple graph has no loops and no multiple edges.
In an undirected graph, edges have no direction; in a directed graph, edges go one way.
Two vertices are adjacent if they share an edge.
An edge is incident to the vertices it touches.
The degree of a vertex, written as $\deg(v)$, is the number of incident edges.
An isolated vertex has degree $0$; a leaf has degree $1$.
In a directed graph, use in-degree and out-degree.
For an undirected graph, $\sum_{v \in V} \deg(v) = 2|E|$.
A walk may repeat vertices and edges.
A path does not repeat vertices.
A cycle starts and ends at the same vertex and does not repeat other vertices.
A graph is connected if there is a path between every pair of vertices.
A connected component is a maximal connected subgraph.
Graph terminology is essential for Midterm 1 and for solving Intro to Graph Theory problems accurately.