STEP-BY-STEP LESSON · §1.4
The Language of Graphs
Read vertices and edges as a description of connections.
Before you begin
The Language of Sets
A set specifies which objects are included. Listing order and repetition do not change it.
{2,5}={5,2,2}5∈A asks about the number 5. {5}⊆A asks whether every element of {5} belongs to A.
5∈{2,5}; {5}⊆{2,5}Symbols
- V
- vertex set
- E
- edge set
- deg(v) / N(v)
- degree / set of neighbors of vertex v
Definitions and notation for this topic
Graph
G=(V,E)
A structure consisting of vertices and edges connecting vertices.
This example is a simple undirected graph.
For a simple undirected graph, each edge is a two-element vertex set. With loops or parallel edges, retain named edges and their endpoint information; the simple encoding alone is insufficient.
Separate glossary example
V={A,B,C}, E={{A,B},{B,C}}
Vertex / node
v ∈ V
One of the objects in a graph.
This is a tutor example.
Separate glossary example
A station on a subway map can be represented by a vertex.
Edge
e ∈ E
A connection between vertices.
In a directed graph, an edge has a direction.
Separate glossary example
An edge connects A and B: A—B.
Loops and parallel edges
A loop has the same endpoint twice. Parallel edges are distinct edges with the same endpoints. For an undirected multigraph, retain each edge’s identity and endpoint pair.
A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.
Separate glossary example
e₁=AB and e₂=AB are two edges, not one duplicated set entry. A loop e₃=AA contributes two to deg(A).
Degree
deg(v)
In a simple undirected graph, the number of edges incident with a vertex.
In a graph allowing loops, a loop contributes 2 to the degree.
Separate glossary example
In A—B—C, deg(B)=2.
Neighbours and connectedness
N(v)
In a simple undirected graph, N(v) is the set of vertices adjacent to v. The graph is connected when every pair of vertices is joined by a path.
Adjacency means one edge; connectedness permits a longer path. In this simple graph deg(v)=|N(v)|; parallel edges and loops require separate degree conventions.
Separate glossary example
In the path A—B—C, N(B)={A,C}; the graph is connected even though A and C are not adjacent.
Bipartite graph
V=A∪B, A∩B=∅
A graph whose vertices can be split into two disjoint sets so every edge joins the two sets.
Every edge joins one vertex in A to one in B. The optional symbol A⊔B means disjoint union; the two equations above state that condition explicitly.
Separate glossary example
Students connected to the dishes they choose.
Step by step
Step 1 / 6
What a graph describes
Vertices represent objects; edges represent selected connections. First specify directions and whether loops or parallel edges are allowed.
G=(V,E)
The conventions determine admissible connections.
Worked example
For a simple undirected graph V={a,b,c,d}, E={ab,bc}, find all degrees and whether a is adjacent to c.
- Edge ab touches a and b; edge bc touches b and c. Count these ends at each vertex.
- The degrees are deg(a)=1, deg(b)=2, deg(c)=1, deg(d)=0. d still belongs to V even with no edge.
- ac is not in E, so a and c are not adjacent. The two-edge route a,b,c answers a different question.
Optional self-check
Are a and c directly adjacent?
Show answer
No: edge ac is absent, although a route through b exists.