What Is a Network (Graph)?

A network (or graph) is a collection of points called vertices (or nodes) connected by lines called edges. Networks model real-world connections such as road systems, social networks, and computer networks.

Visual: A Simple Network

This graph has 5 vertices (A, B, C, D, E) and 7 edges.

The degree of a vertex is the number of edges connected to it. In the graph above, vertex A has degree 3 (connected to B, C, and D via the diagonal). The sum of all degrees always equals twice the number of edges (the Handshaking Lemma).

Paths, Trails, and Circuits

Traversing a network means moving along edges from one vertex to another. Different types of traversals have specific names:

Path

A sequence of edges where no vertex is repeated. It starts and ends at different vertices. Example: A - B - D.

Circuit (Cycle)

A path that starts and ends at the same vertex with no repeated edges. Example: A - B - D - C - A.

Eulerian Trail

A trail that uses every edge exactly once. Exists if and only if the graph has exactly 0 or 2 vertices of odd degree.

Eulerian Circuit

A circuit that uses every edge exactly once and returns to the start. Exists if and only if every vertex has even degree.

Connected Graphs and Components

A graph is connected if there is a path between every pair of vertices. If some vertices cannot be reached from others, the graph is disconnected and consists of two or more components.

Handshaking Lemma: In any graph, the sum of all vertex degrees equals twice the number of edges.

∑ deg(v) = 2 × |E|

This means the number of vertices with odd degree must always be even.

Key Vocabulary

Vertex (Node)

A point in a network that can be connected to other points by edges.

Edge

A line segment connecting two vertices in a network.

Degree

The number of edges connected to a vertex. A loop contributes 2 to the degree.

Connected Graph

A graph where there is a path between every pair of vertices; no vertex is isolated.

Worked Examples

1

A graph has vertices P, Q, R, S with edges PQ, PR, QR, QS, RS. Find the degree of each vertex and verify the Handshaking Lemma.

Step 1: Count edges at each vertex. deg(P) = 2 (PQ, PR), deg(Q) = 3 (PQ, QR, QS), deg(R) = 3 (PR, QR, RS), deg(S) = 2 (QS, RS).

Step 2: Sum of degrees = 2 + 3 + 3 + 2 = 10. Number of edges = 5.

Answer: 10 = 2 × 5 ✓ The Handshaking Lemma is verified. The graph has 2 vertices of odd degree (Q and R).

2

Does the graph from Example 1 have an Eulerian trail or an Eulerian circuit?

Step 1: Count vertices of odd degree. Q and R have odd degree (3 each). That gives us exactly 2 vertices with odd degree.

Step 2: For an Eulerian circuit, all vertices must have even degree (not the case). For an Eulerian trail, exactly 2 vertices must have odd degree (this is the case).

Answer: The graph has an Eulerian trail starting at Q and ending at R (or vice versa), but no Eulerian circuit.

3

A network has 6 vertices. Each vertex has degree 4. How many edges does the network have?

Step 1: Sum of degrees = 6 × 4 = 24.

Step 2: By the Handshaking Lemma, ∑deg = 2|E|, so |E| = 24/2 = 12.

Answer: The network has 12 edges.

Knowledge Check

Select the correct answer for each question. Click "Check Answer" to see if you are right.

Question 1

A graph has 4 vertices with degrees 2, 3, 3, and 4. How many edges does it have?

5 6 12 4

Question 2

Which condition is required for a graph to have an Eulerian circuit?

Exactly 2 vertices have odd degree All vertices have odd degree All vertices have even degree The graph has no edges

Question 3

A connected graph has 5 vertices and 7 edges. What is the sum of all vertex degrees?

7 12 35 14

Question 4

A graph has vertices with degrees: 2, 2, 4, 4. Can an Eulerian trail exist?

Yes, and in fact an Eulerian circuit also exists No, because there are no odd-degree vertices Yes, because all degrees are even Not enough information

Question 5

What is the degree of a vertex that has a loop (an edge connecting to itself) and two other edges?

2 4 3 5

Introduction to Networks