Graph Properties

Degree, connectivity, and special graph types

Graph Properties

Now that you understand the basic structure of graphs, let's explore their properties. These characteristics help us classify graphs, prove theorems, and understand the behavior of networks.

In this section, you'll discover the elegant Handshaking Lemma, learn about connectivity, and meet some famous graph families!

What You'll Learn

📊
Vertex Degree
Measure how connected each vertex is
🤝
Handshaking Lemma
A beautiful theorem about degree sums
🔗
Connected Components
Identify separate parts of a graph
⭐
Special Graph Types
Complete, cycle, path, star, and bipartite graphs

Degree Calculator

The degree of a vertex is the number of edges connected to it. Click a vertex, then click another to add or remove an edge between them.

Degree Sequence

33222

Sorted list of all vertex degrees

2
Min Degree (δ)
3
Max Degree (Δ)
Not Regular
Vertices have different degrees

How to Use

  • Click a vertex to select it, then click another to toggle an edge
  • Watch how degrees update in real-time
  • Purple vertices have minimum degree, amber have maximum
  • Try making all degrees equal to create a regular graph!

The Handshaking Lemma

The Handshaking Lemma states that the sum of all vertex degrees equals twice the number of edges. Why? Because each edge contributes +1 to the degree of both its endpoints!

Click two vertices to add an edge between them

The Handshaking Lemma

Σ deg(v) = 2|E|

Sum of Degrees

++++=6

Verification

2 × |E| = 2 × 3 =6
✓ 6 = 6 — Lemma verified!

Why It Works

Each edge has exactly two endpoints. When we count degrees, we're counting how many times each vertex appears as an endpoint. Since each edge contributes to two endpoint counts, the sum of degrees is exactly twice the number of edges.

Corollary: The sum of degrees in any graph is always even. This means the number of vertices with odd degree must be even!

Connected Components

A graph can have multiple connected components — groups of vertices where you can reach any vertex from any other within the same group. Isolated vertices form their own component!

Click two vertices to toggle an edge between them

Key Concepts

  • Connected: Two vertices are connected if there's a path between them
  • Component: A maximal set of vertices where every pair is connected
  • Isolated vertex: A vertex with no edges forms its own component
  • A graph is connected if it has exactly one component

Special Graph Types

These fundamental graph families appear everywhere in mathematics and computer science. Each has unique properties and applications.

Complete Graph

K5

Every vertex is connected to every other vertex

Properties

Vertices (|V|)5
Edges (|E|)10
Edge Formulan(n-1)/2
Regular?Yes (4-regular)

Quick Reference

Kn — n(n-1)/2 edges
Cn — n edges, 2-regular
Pn — n-1 edges, not regular
Sn — n leaves, 1 center
Km,n — m×n edges (bipartite)

What We've Learned

1. Vertex Degree: The degree of a vertex counts its incident edges. The degree sequence (sorted list of degrees) characterizes a graph. Regular graphs have all vertices with the same degree.

2. Handshaking Lemma: The sum of all degrees equals 2|E|. Each edge contributes to two endpoint degrees. Corollary: the number of odd-degree vertices is always even!

3. Connected Components: A graph can have multiple disconnected parts. BFS or DFS can identify all components. A graph is connected if it has exactly one component.

4. Special Graph Types: Complete graphs (Kn), cycles (Cn), paths (Pn), stars (Sn), and bipartite graphs are fundamental families with known properties and formulas.

Next Up: In the next section, you'll learn about trees and forests — graphs with no cycles. You'll discover spanning trees and tree traversal algorithms!