Understanding Graph Order, Size, and Degree

Introduction to Graph Measurements

In graph theory, we need precise ways to describe and measure graphs. Just as we measure physical objects by their dimensions, we measure graphs using specific mathematical properties. Three of the most fundamental properties are order, size, and degree. Understanding these concepts is crucial for analyzing graph structures and solving complex problems.

Let’s explore these concepts step by step with interactive examples!

Order of a Graph

The order of a graph is simply the number of vertices (nodes) it contains. We denote the order of graph $G$ as $|V|$ or sometimes just $n$.

Definition: If $G = (V, E)$ is a graph, then the order of $G$ is $|V|$, the number of vertices.

Example: A Graph of Order 4

Here’s a simple graph with 4 vertices:

This graph has:
- Order = 4 (vertices: A, B, C, D)
- Size = 3 (edges: AB, BC, CD)

The order tells us how many “entities” or “objects” we’re working with in our graph.

Size of a Graph

The size of a graph is the number of edges it contains. We denote the size of graph $G$ as $|E|$ or sometimes just $m$.

Definition: If $G = (V, E)$ is a graph, then the size of $G$ is $|E|$, the number of edges.

Maximum Possible Size

An interesting question arises: What is the maximum number of edges a graph can have?

For a simple undirected graph (no loops, no multiple edges) with $n$ vertices, the maximum size is:

$$\text{Maximum Size} = \frac{n(n-1)}{2} = \binom{n}{2}$$

But why?

Think of it this way: the maximum number of edges equals the number of ways to select two vertices from $n$ vertices.

Let’s break down the reasoning:

1. Select the first vertex $a$: We have $n$ choices
2. Select the second vertex $b$: We have $n-1$ remaining choices
3. This gives us $n(n-1)$ ways to select two vertices

BUT WAIT! We’ve counted each edge twice!

The edge between vertices $a$ and $b$ is the same as the edge between $b$ and $a$.

In an undirected graph, $ab$ and $ba$ represent the same edge.

Therefore, we divide by 2:

$$\frac{n(n-1)}{2}$$

Example: Complete Graph K₄

A complete graph $K_n$ is a graph where every vertex is connected to every other vertex—it has the maximum possible size!

For $K_4$:
- Order = 4 vertices
- Maximum Size = $\frac{4(4-1)}{2} = \frac{12}{2} = 6$ edges

Count them: AB, AC, AD, BC, BD, CD — exactly 6 edges!

Degree of a Vertex

The degree of a vertex is one of the most important concepts in graph theory. It tells us how “connected” a vertex is.

Definition: The degree of a vertex $v$, denoted $\deg(v)$, is the number of edges incident to (touching) that vertex.

In simpler terms: The degree tells us how many neighbors a vertex has.

Special Cases

Isolated Vertices

A vertex with degree 0 is called an isolated vertex — it’s a lone wolf, not connected to anyone!

In this graph:

• Vertex F is isolated: $\deg(F) = 0$
• Vertex A has the highest degree: $\deg(A) = 3$
• Vertices B and C: $\deg(B) = 2$, $\deg(C) = 2$
• Vertices D and E: $\deg(D) = 2$, $\deg(E) = 1$

Minimum and Maximum Degree

For any graph $G$, we define:

• $\delta(G)$ (small delta) = the minimum degree in the graph
• $\Delta(G)$ (big delta) = the maximum degree in the graph

Memory Tip: Think of $\delta$ as the “small delta” for minimum, and $\Delta$ as the “BIG DELTA” for maximum!

In this graph:

• $\delta(G) = 1$ (vertices v1 and v4 each have degree 1)
• $\Delta(G) = 4$ (the center vertex has degree 4)

Important Note: $\delta$ and $\Delta$ are properties of the entire graph, while $\deg(v)$ is a property of a single vertex.

Regular Graphs

A graph where every vertex has the same degree is called a regular graph. If every vertex has degree $k$, we call it a k-regular graph.

This is a 2-regular graph (also called a cycle graph):

• Every vertex has exactly degree 2
• $\delta(G) = \Delta(G) = 2$

Degree Sequence

The degree sequence of a graph is a list of the degrees of all vertices, typically written in non-increasing order (from largest to smallest).

Definition: The degree sequence of graph $G$ is the list $(d_1, d_2, ..., d_n)$ where $d_1 \geq d_2 \geq ... \geq d_n$ and each $d_i = \deg(v_i)$ for some vertex $v_i$.

Example: Finding a Degree Sequence

Let’s calculate the degree of each vertex:

• $\deg(v_1) = 3$ (connected to v2, v3, v4)
• $\deg(v_2) = 3$ (connected to v1, v3, v5)
• $\deg(v_3) = 2$ (connected to v1, v2)
• $\deg(v_4) = 1$ (connected to v1)
• $\deg(v_5) = 1$ (connected to v2)
• $\deg(v_6) = 0$ (isolated)

Degree Sequence: $(3, 3, 2, 1, 1, 0)$

Important Property

The degree sequence is unique for each graph, but multiple different graphs can have the same degree sequence!

The Handshaking Lemma

One of the most elegant results in graph theory is the Handshaking Lemma (also called the Degree Sum Formula).

Theorem (Handshaking Lemma): The sum of all vertex degrees equals twice the number of edges.

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

Why Is This True?

The reasoning is beautifully simple:

1. Each edge connects exactly two vertices
2. When we count degrees, each edge contributes to the degree of both its endpoints
3. Therefore, each edge is counted exactly twice in the degree sum

Verification Example

Let’s verify the Handshaking Lemma:

Degrees:
- $\deg(A) = 3$
- $\deg(B) = 2$
- $\deg(C) = 3$
- $\deg(D) = 2$

Sum of degrees: $3 + 2 + 3 + 2 = 10$

Number of edges: 5

Verification: $2 \times 5 = 10$ ✓

The sum of degrees equals twice the number of edges!

Corollary: Even Sum Property

An immediate consequence of the Handshaking Lemma is:

The sum of all vertex degrees in any graph is always even.

This is because $2|E|$ is always even (it’s 2 times something).

Graphic Sequences

Here’s an intriguing question: Given a sequence of numbers, can we construct a graph with that degree sequence?

Definition: A sequence of non-negative integers is called a graphic sequence if there exists a simple graph whose degree sequence is that sequence.

In other words, can we draw a graph where the vertices have exactly these degrees?

Example 1: A Graphic Sequence

Consider the sequence $(3, 3, 2, 1, 1, 0)$.

This IS graphic! We can construct a graph with this degree sequence (as shown above).

Note: The sequence remains graphic even if we remove the 0: $(3, 3, 2, 1, 1)$

Example 2: A Non-Graphic Sequence (Too Many Connections)

Consider the sequence $(4, 3, 2, 1)$.

This is NOT graphic. Why?

• The first vertex needs degree 4, meaning it must connect to 4 other vertices
• But we only have 3 other vertices available!
• It’s impossible to satisfy this requirement

In the visualization above, even connecting v1 to all other vertices only gives it degree 3, not 4!

Example 3: A Non-Graphic Sequence (Odd Sum)

Consider the sequence $(4, 3, 3, 2, 2, 1)$.

This is NOT graphic. Why?

Let’s sum the degrees: $4 + 3 + 3 + 2 + 2 + 1 = 15$

By the Handshaking Lemma, the sum of degrees must equal $2|E|$, which is always even. Since 15 is odd, this sequence cannot be graphic!

Necessary Conditions for Graphic Sequences

For a sequence $(d_1, d_2, ..., d_n)$ to be graphic:

1. Even Sum: $\sum d_i$ must be even (by Handshaking Lemma)
2. Degree Constraint: Each $d_i < n$ (a vertex can’t connect to more vertices than exist)
3. Non-negativity: All $d_i \geq 0$

These conditions are necessary but not sufficient—there are sequences that satisfy all three but still aren’t graphic!

The Erdős–Gallai Theorem

There is a complete characterization of graphic sequences called the Erdős–Gallai theorem, but that’s a topic for advanced study. For now, remember:

A sequence of all zeros is always graphic (the empty graph or a graph with isolated vertices).

Practical Applications

Understanding order, size, and degree has real-world applications:

Social Networks

• Degree represents how many friends/connections a person has
• High-degree vertices are “influencers” or “hubs”
• $\Delta(G)$ identifies the most connected person

Computer Networks

• Degree represents how many direct connections a router has
• Higher degree = more redundancy and reliability
• But also higher cost and complexity

Biological Networks

• In protein interaction networks, degree indicates how many other proteins a given protein interacts with
• High-degree proteins are often essential for organism survival

Web Graphs

• Webpages are vertices, hyperlinks are edges
• Degree (specifically out-degree in directed graphs) indicates how many links a page has
• Google’s PageRank algorithm uses degree-based concepts

Practice Problems

Test your understanding with these problems:

Problem 1: A graph has 10 vertices and degree sequence $(3, 3, 3, 3, 2, 2, 2, 2, 2, 2)$. How many edges does it have?

Problem 2: Is the sequence $(5, 4, 3, 2, 1)$ graphic?

Problem 3: What is the maximum possible size of a graph with 8 vertices?

Problem 4: In a graph with 6 vertices, if $\delta(G) = 2$, what is the minimum number of edges?

Summary

Let’s recap the key concepts we’ve covered:

Basic Definitions:
- Order $|V|$: Number of vertices in the graph
- Size $|E|$: Number of edges in the graph
- Maximum Size: $\frac{n(n-1)}{2}$ for $n$ vertices (complete graph)

Degree Concepts:
- Degree $\deg(v)$: Number of edges touching vertex $v$
- Isolated Vertex: A vertex with degree 0
- $\delta(G)$: Minimum degree in graph $G$
- $\Delta(G)$: Maximum degree in graph $G$

Advanced Topics:
- Degree Sequence: List of all vertex degrees in non-increasing order
- Handshaking Lemma: $\sum \deg(v) = 2|E|$ (sum of degrees equals twice the number of edges)
- Graphic Sequence: A sequence that can be realized as the degree sequence of some graph

These fundamental concepts form the building blocks for understanding more advanced graph theory topics. Master them, and you’ll have a solid foundation for exploring algorithms, optimization problems, and complex network analysis!

Explore More

Ready to create your own graphs and experiment with these concepts?

👉 Visit the GraphArena Playground to build graphs and calculate their properties interactively!

Try creating graphs with different degree sequences and see if you can verify the Handshaking Lemma yourself!