Skip to content
Tutorials Center
My learning

Topics

Lesson 2 of 36 ยท Getting Started

Graph Terminology

Learn the core vocabulary of graph theory: degree, neighbors, isolated vertices, regular graphs and the handshake lemma, with runnable Python examples that check each rule.

Graph theory has a compact vocabulary. Learn the words once and every later lesson reads easily. This lesson covers the terms you will use constantly: degree, neighbors, isolated vertices, regular graphs, sparse and dense graphs, and the first theorem of the subject, the handshake lemma.

It builds on What Is a Graph?, where we defined G = (V, E).

Degree

The degree of a vertex v, written deg(v) or d(v), is the number of edges incident to it. In a simple graph (no loops, no repeated edges) it is also the number of neighbors.

graph LR
  a --- b
  a --- c
  a --- d
  b --- c
  e

Here deg(a) = 3, deg(b) = 2, deg(c) = 2, deg(d) = 1, deg(e) = 0.

Special names:

  • Isolated vertex: degree 0 (the vertex e above).
  • Leaf (or pendant vertex): degree 1 (d).
  • Minimum degree ฮด(G) and maximum degree ฮ”(G): the smallest and largest degrees in the graph. Here ฮด = 0 and ฮ” = 3.
  • The degree sequence lists all degrees, usually from largest to smallest: (3, 2, 2, 1, 0).
Python Degrees and the degree sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The handshake lemma

Every edge has two ends, and each end adds 1 to the degree of one vertex. So if you add up all the degrees, you count every edge exactly twice:

TEXT
sum of deg(v) over all v  =  2 * |E|

This is the handshake lemma: at a party, the total number of hands shaken (counted per person) is twice the number of handshakes. Two consequences you can use immediately:

  1. The sum of degrees is always even.
  2. Therefore the number of vertices with odd degree is always even. (A sum of numbers is even only if an even number of them are odd.)

This is why no graph can have exactly three vertices of odd degree. It also lets you reject impossible degree sequences: (3, 3, 3) cannot be a graph because its sum is 9, which is odd.

Python Checking the handshake lemma

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Regular, complete and empty graphs

A graph is k-regular if every vertex has degree k. A triangle is 2-regular. The cube (8 corners, 12 edges) is 3-regular. A 3-regular graph is called cubic.

By the handshake lemma, a k-regular graph on n vertices has exactly nยทk/2 edges, so nยทk must be even. A 3-regular graph on 5 vertices does not exist.

A complete graph K_n has an edge between every pair of vertices. It is (n-1)-regular and has n(n-1)/2 edges. The empty graph has vertices but no edges.

Sparse versus dense

A simple graph on n vertices can have at most n(n-1)/2 edges. If m is close to that maximum the graph is dense; if m grows roughly like n the graph is sparse. Road networks are sparse (each intersection touches few roads). A graph of "who has ever exchanged a message with whom" in a small chat room can be dense. This distinction decides which representation is best.

Python Density of a graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Neighborhoods

The neighborhood N(v) is the set of neighbors of v. The closed neighborhood N[v] also includes v. In a simple graph, deg(v) = |N(v)|. Many algorithms (searching, coloring, clustering) work by repeatedly asking "who are the neighbors of this vertex?".

Common mistakes

  • Forgetting that a vertex with no edges still counts as a vertex (it is isolated, degree 0).
  • Claiming a degree sequence is valid without checking that its sum is even.
  • Mixing up n (vertices) and m (edges) in formulas such as m = nยทk/2.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A graph has degree sequence (4, 3, 3, 2, 2). How many edges does it have?

    The degrees sum to 14, and by the handshake lemma the sum is 2m, so m = 7.
  2. 2. Which degree sequence is impossible for any graph?

    (3, 3, 3) sums to 9, which is odd, but the sum of degrees must equal 2m, an even number.
  3. 3. How many edges does the complete graph K8 have?

    K_n has n(n-1)/2 edges, so 8*7/2 = 28.
  4. 4. A vertex of degree 0 is called:

    Degree 0 means no incident edges: the vertex is isolated. A leaf has degree 1.

Summary

  • deg(v) is the number of edges at v; ฮด(G) and ฮ”(G) are the minimum and maximum degrees.
  • Handshake lemma: the sum of all degrees equals 2m, so the number of odd-degree vertices is even.
  • A k-regular graph has nk/2 edges; K_n has n(n-1)/2 edges.
  • Dense and sparse graphs call for different data structures.
  • The neighborhood N(v) is the set of vertices adjacent to v.

Next: Kinds of Graphs