Graph Theory — Vertices, Edges & Basic Concepts

Graph theory is the study of graphs, which are structures made of vertices and edges. A vertex is an object, and an edge shows a relationship between two objects.

If you are searching for graph theory basics, start with this idea: a graph is a clean way to model connections. People in a social network, cities joined by roads, and web pages linked to each other can all be represented with graphs.

What A Graph Means In Math

In an undirected graph, an edge says two vertices are connected, and the connection has no direction. If $A$ is joined to $B$, then $B$ is also joined to $A$.

In a directed graph, edges do have direction, so $A \to B$ and $B \to A$ are different statements. Many beginner examples use simple undirected graphs, which means no loops and no repeated edges between the same two vertices.

That condition matters because definitions are often introduced in the simple, undirected setting first. If the graph type changes, the meaning of terms can change too.

Basic Graph Theory Terms You Need First

Vertices and edges

A vertex is the thing you want to track. An edge is the connection you want to track.

If a graph models cities and roads, the cities are vertices and the roads are edges.

Degree

In an undirected graph, the degree of a vertex is the number of edges touching it.

If one city has roads to three other cities, its degree is $3$.

Path

A path is a sequence of vertices where each consecutive pair is connected by an edge.

If there is a path from one vertex to another, you can move from one to the other by following edges.

Cycle

A cycle is a path that starts and ends at the same vertex. In the usual basic definition, no other vertex is repeated.

A cycle shows that there is a closed loop in the graph.

Connected graph and connected components

An undirected graph is connected if every vertex can be reached from every other vertex by some path.

If that fails, the graph splits into connected components. Each component is a connected piece of the graph.

Worked Example: One Small Graph

Suppose a graph has vertices $A$, $B$, $C$, $D$, and $E$, with edges

$$AB,\ AC,\ BC,\ CD$$

This gives a triangle on $A$, $B$, and $C$, one extra edge from $C$ to $D$, and an isolated vertex $E$.

Now the main ideas are easy to see.

The degrees are

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

There is a path from $A$ to $D$:

$$A-C-D$$

There is a cycle:

$$A-B-C-A$$

The graph is not connected because $E$ cannot be reached from the other vertices. So the graph has two connected components: one containing $A,B,C,D$ and one containing only $E$.

This single example shows how degree, path, cycle, isolated vertices, and connected components fit together.

A Fast Check: Sum Of Degrees

For any finite undirected graph,

$$\sum \deg(v) = 2|E|$$

This works because every edge touches exactly two endpoints, so each edge adds $1$ to two degree counts.

In the example above, the degree sum is

$$2+2+3+1+0=8$$

and the number of edges is $4$, so

$$2|E| = 2 \cdot 4 = 8$$

This is a useful check when you count degrees by hand. If the numbers do not match, something is wrong.

Common Graph Theory Mistakes

Mixing up vertices and edges

Vertices are the objects. Edges are the relationships between them.

Forgetting what kind of graph you have

A statement that is true for a simple undirected graph may need to be changed for a directed graph or for a graph that allows loops.

Treating a path like a cycle

A path does not have to return to where it started. A cycle does.

Ignoring isolated vertices

A vertex with degree $0$ is still part of the graph. It can change whether the graph is connected.

Where Graph Theory Basics Are Used

These ideas appear in computer networks, route planning, scheduling, recommendation systems, and social networks. The context changes, but the same questions keep coming up: what is connected, what can be reached, and where are the loops?

That is why graph theory shows up early in both discrete math and computer science.

Try A Similar Graph

Draw four vertices $P$, $Q$, $R$, and $S$. Add edges $PQ$, $QR$, $RS$, and $SP$.

Then answer three questions: what is the degree of each vertex, is the graph connected, and does the graph contain a cycle?