The Central Idea
A graph separates a discrete system into two basic ingredients:
- objects, represented by vertices;
- connections, represented by edges.
A graph may represent roads between cities, friendships between people, hyperlinks between pages, dependencies between tasks, transitions between states, or almost any other pairwise relationship.
The essential abstraction is
\[ \boxed{\text{objects}+\text{connections}}. \]What Is a Graph?
A graph consists of a set of vertices together with a collection of edges connecting those vertices.
A common notation is
\[ G=(V,E), \]where \(V\) is the vertex set and \(E\) is the edge set.
The exact form of the edges depends on whether the graph is directed, undirected, weighted, or allowed to contain special edge types.
Vertices
A vertex is one discrete object or location in a graph.
Vertices are also commonly called nodes.
If
\[ V=\{A,B,C,D\}, \]then the graph contains four vertices.
A vertex may represent a city, person, computer, task, state, webpage, or other object depending on the model.
Edges
An edge records a connection between vertices.
In an undirected graph, an edge between \(A\) and \(B\) may be written
\[ \{A,B\}. \]The order does not matter:
\[ \{A,B\}=\{B,A\}. \]The edge simply says the two vertices are connected.
A Small Graph
Let
\[ V=\{A,B,C,D\} \]and
\[ E= \big\{ \{A,B\}, \{A,C\}, \{B,D\}, \{C,D\} \big\}. \]Then
\[ G=(V,E) \]is a graph with four vertices and four edges.
Adjacency
Two vertices are adjacent when an edge connects them.
If
\[ \{A,B\}\in E, \]then \(A\) and \(B\) are adjacent.
Adjacency records direct connection, not merely indirect reachability.
Incidence
An edge is incident to each vertex it touches.
If
\[ e=\{A,B\}, \]then \(e\) is incident to both \(A\) and \(B\).
Incidence describes the relationship between vertices and edges rather than between two vertices.
Degree
The degree of a vertex in a simple undirected graph is the number of edges incident to that vertex.
It is commonly written
\[ \deg(v). \]If \(A\) is connected directly to \(B\), \(C\), and \(D\), then
\[ \boxed{\deg(A)=3}. \]Isolated Vertices
An isolated vertex has degree zero.
If \(D\) belongs to the vertex set but no edge touches \(D\), then
\[ \deg(D)=0. \]Isolated vertices are still part of the graph even though they have no connections.
Undirected Graphs
In an undirected graph, edges do not have a preferred direction.
A road that can be traveled both ways may be represented by
\[ \{A,B\}. \]The connection from \(A\) to \(B\) is the same edge as the connection from \(B\) to \(A\).
Directed Graphs
In a directed graph, or digraph, an edge has a direction.
A directed edge from \(A\) to \(B\) may be written
\[ (A,B) \]or visually as
\[ A\to B. \]In general,
\[ (A,B)\ne(B,A). \]Directed Edges Are Relations
A directed graph on a vertex set \(V\) can be viewed as a relation
\[ R\subseteq V\times V. \]If
\[ (u,v)\in R, \]then the graph contains the directed edge
\[ u\to v. \]This connects graph theory directly to the previous lesson on relations.
In-Degree and Out-Degree
In a directed graph, we distinguish incoming and outgoing edges.
The in-degree of \(v\) counts edges pointing into \(v\).
The out-degree counts edges pointing away from \(v\).
For example, if
\[ A\to B,\qquad C\to B,\qquad B\to D, \]then \(B\) has in-degree \(2\) and out-degree \(1\).
Simple Graphs
A simple graph usually means an undirected graph with no loops and no multiple edges between the same pair of vertices.
For distinct vertices \(u\) and \(v\), there is either no edge or one edge connecting them.
Simple graphs provide the standard introductory model for many graph-theory problems.
Loops
A loop is an edge connecting a vertex to itself.
In directed notation, a loop at \(A\) is
\[ (A,A). \]Some graph models allow loops and others forbid them.
The modeling rules must therefore be specified.
Multiple Edges
Some graph models allow more than one edge between the same pair of vertices.
For example, two cities might be connected by several distinct airline routes or rail lines.
Such a structure is often called a multigraph.
When only one edge is allowed, the graph is structurally simpler.
Weighted Graphs
A weighted graph assigns a numerical value to an edge or sometimes to a vertex.
An edge weight might represent
- distance;
- travel time;
- cost;
- capacity;
- risk;
- probability;
- strength of connection.
Weighted graphs turn connectivity into quantitative structure.
Example: Transportation Network
Suppose vertices represent cities and edges represent direct roads.
An edge
\[ \{A,B\} \]might carry the weight
\[ 120 \]to indicate a distance of \(120\) kilometers.
The resulting weighted graph can support routing and optimization problems.
What Is a Network?
A network is generally a graph interpreted as a system of meaningful connections.
Examples include
- transportation networks;
- communication networks;
- social networks;
- electrical networks;
- supply networks;
- dependency networks.
The term emphasizes application and interaction rather than only abstract graph structure.
Paths
A path follows a sequence of connected vertices.
For example,
\[ A,B,C,D \]describes a path when the graph contains edges connecting each consecutive pair:
\[ A-B,\qquad B-C,\qquad C-D. \]Paths describe possible routes through a graph.
Path Length
In an unweighted graph, the length of a path is commonly the number of edges traversed.
The path
\[ A-B-C-D \]uses three edges.
Therefore its length is
\[ \boxed{3}. \]Weighted Path Length
In a weighted graph, path cost may instead be the sum of its edge weights.
If a path uses edges with weights
\[ 4,\quad7,\quad3, \]then its total weight is
\[ \boxed{4+7+3=14}. \]The meaning of the total depends on what the weights represent.
Walks and Trails
Graph theory distinguishes several related kinds of routes.
A walk may revisit vertices and edges.
A trail does not repeat edges.
A path, in common introductory usage, does not repeat vertices.
Later graph lessons will develop these distinctions more formally.
Cycles
A cycle is a route that returns to its starting vertex without merely retracing the same structure.
For example,
\[ A-B-C-A \]forms a cycle when all three required edges exist.
Cycles are fundamental in graph structure, scheduling, circuits, and state systems.
Connectivity
Two vertices are connected when some path joins them.
A graph is connected when every pair of vertices can be joined by a path.
Connectivity describes global reachability rather than direct adjacency.
Adjacency versus Connectivity
Adjacent vertices share an edge directly.
Connected vertices need only be joined by some path.
Thus \(A\) and \(D\) may not be adjacent but may still be connected through
\[ A-B-C-D. \]Direct connection and indirect reachability are different concepts.
Connected Components
A graph that is not connected can break into separate connected components.
Within each component, vertices can reach one another.
No path connects vertices belonging to different components.
Components identify independent pieces of a discrete system.
What Is a Tree?
A tree is a connected undirected graph with no cycles.
Trees represent branching structures without circular routes.
They appear in
- hierarchies;
- decision processes;
- file systems;
- search procedures;
- taxonomies;
- network design.
A Small Tree
Consider the edges
\[ \{A,B\},\qquad \{A,C\},\qquad \{C,D\}. \]The resulting graph is connected.
It contains no cycle.
Therefore it is a tree.
Unique Paths in Trees
In a tree, exactly one simple path connects any two vertices.
If two distinct simple paths connected the same two vertices, the two routes would create a cycle.
This unique-path property is one of the most useful structural features of trees.
Edges in a Finite Tree
A finite tree with \(n\) vertices has
\[ \boxed{n-1} \]edges.
For example, a tree with \(6\) vertices has
\[ 5 \]edges.
This fact will later be proved and used repeatedly.
Rooted Trees
A rooted tree designates one vertex as the root.
The root establishes a directional hierarchy even when the underlying graph is undirected.
Other vertices can then be described relative to their position below or above one another.
Parent and Child
In a rooted tree, a vertex directly below another may be called its child.
The vertex immediately above is the parent.
If \(A\) is the parent of \(B\), then \(B\) is a child of \(A\).
These terms describe hierarchy rather than biological meaning.
Ancestors and Descendants
A vertex lying above another along the unique route toward the root is an ancestor.
A vertex lying below another is a descendant.
These relationships are common in organizational charts, file systems, and recursive data structures.
Leaves
A leaf in a rooted tree is a vertex with no children.
Leaves represent endpoints of branches.
In a decision tree, leaves may represent final outcomes.
In a search tree, they may represent states with no further expansion.
Depth
The depth of a vertex is commonly the number of edges from the root to that vertex.
The root therefore has depth
\[ 0. \]Its children have depth
\[ 1, \]and so on.
Levels
Vertices having the same depth are often said to lie on the same level.
Levels organize a rooted tree into horizontal layers:
\[ 0,1,2,3,\ldots \]This organization is useful for breadth-first traversal and hierarchical reasoning.
Binary Trees
A binary tree is a rooted tree in which each vertex has at most two children.
The children are often distinguished as
\[ \text{left} \]and
\[ \text{right}. \]Binary trees are central in searching, sorting, expression parsing, and decision structures.
Decision Trees
A decision tree represents a sequence of choices or tests.
Internal vertices represent decisions.
Edges represent possible responses or outcomes.
Leaves represent final states or conclusions.
Decision trees connect discrete structure to counting and algorithmic reasoning.
Dependency Trees and Graphs
Tasks may depend on other tasks.
If task \(B\) cannot begin until task \(A\) finishes, we might represent
\[ A\to B. \]Many dependency systems are directed graphs rather than trees because one task may have several prerequisites and several downstream dependents.
What Is a State?
A state is a complete description of the information needed to characterize a system at a particular stage of a model.
A state might be
- a position in a game;
- a machine mode;
- a queue length;
- a configuration of switches;
- a location in a process;
- a partial solution in an algorithm.
State Space
The state space is the set of all states allowed by the model.
For a single switch,
\[ S=\{\text{off},\text{on}\}. \]For three binary switches,
\[ |S|=2^3=8. \]State spaces may be finite or countably infinite.
State-Transition Graphs
A state-transition graph represents states as vertices and allowed transitions as directed edges.
If a system can move from state \(A\) to state \(B\), draw
\[ A\to B. \]If the reverse transition is also allowed, include
\[ B\to A. \]Deterministic State Transitions
A deterministic update rule assigns one next state to each current state.
Thus the transition rule can be modeled as a function
\[ f:S\to S. \]Each state has exactly one outgoing transition under that rule.
Repeated application creates a sequence of states.
Example: A Three-State Cycle
Let
\[ S=\{A,B,C\} \]with
\[ A\to B,\qquad B\to C,\qquad C\to A. \]Starting at \(A\), the state sequence is
\[ A,B,C,A,B,C,\ldots \]The graph therefore contains a directed cycle.
Nondeterministic State Transitions
Some systems permit several possible next states.
From state \(A\), the system might allow
\[ A\to B \]and
\[ A\to C. \]The transition structure is then a relation rather than a single-valued function.
Reachability
A state \(B\) is reachable from state \(A\) when some directed path leads from \(A\) to \(B\).
Reachability asks whether a transition sequence exists.
This becomes a central question in algorithms, automata, games, workflows, and verification.
Terminal States
A terminal state has no allowed outgoing transition in the model.
In a game tree, it might represent the end of the game.
In an algorithm, it might represent completion.
In a process model, it might represent an absorbing or final condition.
Graphs as Pictures and as Mathematics
The visual drawing of a graph is not the graph itself.
The graph is determined by its vertices and connections.
The same graph may be drawn in many different layouts without changing its structure.
This distinction is fundamental: geometry of the drawing is often irrelevant unless the model explicitly includes geometric information.
Moving a Vertex Does Not Change an Abstract Graph
Suppose a graph drawing places \(A\) above \(B\).
Moving \(A\) to the left side of the page does not alter the graph as long as the same edges remain.
Abstract graph structure depends on adjacency, not page coordinates.
Edge Crossings Do Not Automatically Create Vertices
Two drawn edges may cross on the page without being connected.
A crossing represents a vertex only when the graph explicitly identifies a vertex there.
This differs from some physical network diagrams where intersections may have practical meaning.
Adjacency Lists
An adjacency list records the neighbors of each vertex.
For example:
| Vertex | Adjacent vertices |
|---|---|
| A | B, C |
| B | A, D |
| C | A, D |
| D | B, C |
Adjacency lists are efficient representations for many sparse graphs.
Adjacency Matrices
A finite graph can also be encoded in a matrix.
For vertices
\[ v_1,\ldots,v_n, \]define
\[ A_{ij}= \begin{cases} 1,&v_i\text{ is adjacent to }v_j,\\ 0,&\text{otherwise}. \end{cases} \]The result is an adjacency matrix.
Symmetry of an Undirected Adjacency Matrix
In an undirected graph,
\[ v_i\text{ adjacent to }v_j \]implies
\[ v_j\text{ adjacent to }v_i. \]Therefore the adjacency matrix satisfies
\[ A_{ij}=A_{ji}. \]It is symmetric across its main diagonal.
Graphs and Incidence Structures
A graph can be viewed as an incidence structure connecting two types of objects:
- vertices;
- edges.
This viewpoint leads naturally to incidence matrices and to broader discrete structures involving points, blocks, sets, and connections.
Subgraphs
A subgraph is formed from some vertices and edges of a larger graph while preserving valid incidence relationships.
Subgraphs allow us to isolate a region or feature of a network.
They are analogous to subsets, but they must respect graph structure.
Induced Subgraphs
If we select a subset of vertices and include every original edge connecting two selected vertices, we obtain an induced subgraph.
The selected vertex set determines which edges remain.
This is useful when examining a group of nodes inside a larger network.
Complete Graphs
A complete graph connects every pair of distinct vertices.
The complete graph on \(n\) vertices is commonly denoted
\[ K_n. \]For example, \(K_3\) forms a triangle.
Complete graphs represent maximal pairwise connectivity in simple graphs.
Bipartite Structure
A graph is bipartite when its vertices can be divided into two groups so that every edge runs between the groups rather than within one group.
This structure appears naturally in assignment problems such as
\[ \text{workers}\leftrightarrow\text{jobs} \]or
\[ \text{students}\leftrightarrow\text{courses}. \]Bipartite graphs will be developed more fully later.
Graphs as Models, Not Reality
A graph records only the information chosen for the model.
A transportation graph may record direct road connections but ignore road width, weather, traffic, elevation, or legal restrictions.
A good graph model therefore depends on selecting the vertices, edges, and attributes relevant to the problem.
Common Error: Confusing a Vertex with Its Label
A vertex label such as
\[ A \]is a name for a graph object.
Changing the label to
\[ X \]does not necessarily change the graph's structure.
Labels identify vertices; connectivity defines the graph.
Common Error: Treating Directed Edges as Undirected
In a directed graph,
\[ A\to B \]does not automatically imply
\[ B\to A. \]Direction is part of the edge data.
Common Error: Confusing Adjacency with Reachability
If
\[ A-B-C, \]then \(A\) and \(C\) are connected by a path.
But they are not adjacent unless the edge
\[ \{A,C\} \]also exists.
Common Error: Calling Every Connected Graph a Tree
A tree must be connected and acyclic.
A connected graph containing
\[ A-B-C-A \]has a cycle.
Therefore it is not a tree.
Common Error: Treating a Drawing Crossing as an Edge Connection
If two graph edges cross visually, the crossing is not automatically a vertex.
Only explicitly defined vertices create connections.
Graph drawings should therefore be read structurally rather than purely visually.
Common Error: Ignoring Edge Weights
In a weighted network, the fewest-edge route is not always the lowest-cost route.
A path with two expensive edges may cost more than a path with four cheap edges.
The optimization criterion must match the meaning of the weights.
Common Error: Assuming a State Diagram Is Deterministic
If one state has several outgoing edges, then the next state may not be uniquely determined without additional information.
A directed state graph can represent a relation rather than a function.
Determinism is an extra structural condition.
A Reliable Procedure for Reading a Graph
- Identify the vertex set.
- Identify the edge set.
- Determine whether edges are directed or undirected.
- Check whether loops or multiple edges are allowed.
- Identify any weights or labels.
- Determine adjacency and incidence relationships.
- Look for paths and reachability.
- Check for cycles.
- Determine whether the graph is connected.
- Identify any special structure such as a tree or state graph.
Example: Classifying a Small Graph
Let
\[ V=\{A,B,C,D\} \]and
\[ E= \big\{ \{A,B\}, \{B,C\}, \{C,D\} \big\}. \]The graph is undirected.
It is connected because every vertex can reach every other vertex.
It has no cycle.
Therefore,
\[ \boxed{G\text{ is a tree}.} \]Example: Classifying a State Graph
Suppose
\[ S=\{0,1,2\} \]with transitions
\[ 0\to1,\qquad 1\to2,\qquad 2\to2. \]This is a directed state graph.
State \(2\) has a loop.
Once the process reaches \(2\), the stated transition rule keeps it at \(2\).
Practice 1: Vertices and Edges
Let
\[ V=\{A,B,C\} \]and
\[ E=\big\{\{A,B\},\{B,C\}\big\}. \]How many vertices and edges does the graph contain?
Practice 2: Degree
Suppose \(A\) is adjacent to \(B\), \(C\), and \(D\), and to no other vertices.
Find
\[ \deg(A). \]Practice 3: Directed Edges
Does
\[ A\to B \]automatically imply
\[ B\to A? \]Practice 4: Path Length
What is the unweighted length of the path
\[ A-B-C-D-E? \]Practice 5: Weighted Path
A path uses edges of weights
\[ 5,\quad2,\quad8. \]What is its total weight?
Practice 6: Tree or Not?
A connected graph contains the cycle
\[ A-B-C-A. \]Can the graph be a tree?
Practice 7: Finite Tree
How many edges does a tree with \(10\) vertices have?
Practice 8: State Space
Four independent switches may each be either off or on.
How many states are possible?
Practice 9: Reachability
Suppose a directed graph contains
\[ A\to B,\qquad B\to C. \]Is \(C\) reachable from \(A\)?
Practice 10: Deterministic or Nondeterministic?
From state \(S\), the system permits both
\[ S\to A \]and
\[ S\to B. \]Does this transition information alone define a deterministic next-state function?
Practice Answers
Practice 1
The graph has
\[ \boxed{3\text{ vertices}} \]and
\[ \boxed{2\text{ edges}}. \]Practice 2
Three edges are incident to \(A\), so
\[ \boxed{\deg(A)=3}. \]Practice 3
No. Directed edges have orientation:
\[ \boxed{A\to B\text{ does not imply }B\to A}. \]Practice 4
The path uses four edges:
\[ \boxed{4}. \]Practice 5
\[ 5+2+8=\boxed{15}. \]Practice 6
No. A tree must contain no cycles.
\[ \boxed{\text{The graph is not a tree}.} \]Practice 7
A finite tree with \(n\) vertices has \(n-1\) edges:
\[ 10-1=\boxed{9}. \]Practice 8
Each switch has two possibilities:
\[ \boxed{2^4=16}. \]Practice 9
Yes. The directed path
\[ A\to B\to C \]shows that
\[ \boxed{C\text{ is reachable from }A}. \]Practice 10
No. State \(S\) has two possible next states.
The transition structure is therefore not a single-valued deterministic next-state function unless an additional rule selects one transition.
What to Remember
- A graph consists of vertices and edges.
- Adjacency describes direct vertex-to-vertex connection.
- Directed edges preserve orientation; undirected edges do not.
- Weights can represent distance, cost, capacity, probability, or other quantities.
- Paths describe routes through graphs.
- Connectivity concerns whether vertices can reach one another.
- A tree is connected and contains no cycles.
- A finite tree with \(n\) vertices has \(n-1\) edges.
- A state graph uses vertices for states and directed edges for allowed transitions.
- The drawing of a graph may change without changing its abstract structure.
The most important abstraction is: identify the discrete objects first, then identify exactly which connections the model allows between them.
Where We Go Next
Graphs organize pairwise connections, but discrete information can also be organized in rectangular, tabular, and incidence-based forms.
The next lesson, Tables, Arrays, and Incidence Structures, develops these representations and shows how finite data and relationships can be encoded systematically.