Types of graphs
We have already discussed some terms that describe different properties of graphs and we have considered directed, undirected and weighted graphs.
This graph is undirected and weighted.
This is a directed weighted graph.
Connected graph
A graph is connected when no vertices or group of vertices are isolated from the rest of the graph. When a part of the graph is isolated, it is said to be disconnected.
The top two graphs are connected, the bottom two are disconnected.
If we remove a bridge from a connected graph the graph will become disconnected.
Complete graph
We call a graph on $n$n vertices complete if every vertex is connected to every other vertex. There is exactly one complete graph for each value of $n$n.
The degree of each individual vertex is equal to one less than the number of vertices overall. In other words, if you take $n$n vertices and connect one to all the others, you draw $n-1$n−1 edges from each vertex.
Simple graph
A graph is called a simple graph if it has:
- no loops, and
- no multiple edges.
The first graph is not simple because it has loops. The second graph is not simple because there are multiple edges between some vertices. The third graph is simple - no vertex is connected to itself, and no vertex is connected to any other in more than one way.
Subgraph
A graph is called a subgraph (or subnetwork) when all vertices and edges are also the vertices and edges of another graph.
If we take a graph and delete some edges, or some of its vertices (and all edges connected to it), we obtain a subgraph of the original.
For example, any simple graph that has $n$n vertices is a subgraph of the complete graph with $n$n vertices - we can just add or delete edges to get from one to the other:
The graph on the left has the red edges added in, and then the vertices moved a little.
We end up with a complete graph.
Bipartite graph
A bipartite graph is a graph whose vertices can be divided into $2$2 groups such that each edge connects a vertex from one group to a vertex in another. Vertices in a group are never connected to other vertices in that group.
You can see the two groups of vertices (top and bottom) and how each edge joins a node from the top group to the bottom group.
A bipartite graph does not have to be drawn in with the groups of vertices arranged in rows (although they usually are).
The graph below is bipartite - the green vertices form one group and the purple vertices form another and all the edges join a green and purple vertex.
| directed graph (digraph) | Edges indicate a one-way relationship and are represented by arrows |
| weighted graph | Edges are assigned a number that can represent some property, such as distance or cost. Weighted graphs may be directed or undirected. |
| connected graph |
No vertices or group of vertices are isolated from the rest of the graph. When a part of the graph is isolated, it is said to be disconnected. |
| complete graph | Every vertex is connected by an edge to every other vertex |
| simple graph | An undirected graph that contains no loops or multiple edges. A simple graph can be connected or disconnected. |
| subgraph | All vertices and edges are also the vertices and edges of another graph. |
| bipartite graph | Vertices can be split into two groups, where each edge connects a vertex from one group to a vertex in the other group. |
Practice questions
Question 1
Consider the following network:
What two changes could be made to make this network simple?
Remove the loop at $B$B.
ARemove an edge between $E$E and $B$B.
BRemove an edge between $C$C and $A$A.
CRemove the loop at $F$F.
D
Question 2
Consider the following two graphs:
 |
 |
| Graph 1 | Graph 2 |
Is Graph 2 a subgraph of Graph 1?
Yes
ANo
B
Question 3
In a connected graph:
There is an isolated vertex.
AThere are no loops.
BEach vertex is linked to another vertex only through one edge.
CEvery vertex is reachable via some path from every other vertex.
D
QUESTION 4
Which of the following graphs are complete bipartite graphs?
Select all that apply.
A
B
C
D