graph theory
Complete graph
A general graph is an ordered set comprised of two subsets that is , , and an incidence function expressed as
Where,
- is a non-empty finite set whose elements are called vertices,
- is a finite set whose elements are called edges, and
- is incidence function relating elements of to elements
In a graph , edge is an element of expressed as
Vertex is an element of expressed as
For instance means that is an edge connecting vertex and another vertex .
A complete graph is a simple graph where each distinct pair vertices are adjacent.
First, a simple graph means that there no loop or parallel edge in the graph.
A loop is an edge that originates and ends in the same vertex.[unique_solution]
A parallel edge is expressed as .
Therefore, in a complete graph .
In order for vertices to be adjacent to each other in a complete graph,
where is a degree of a vertex and is the number of vertices in the graph
Degree of a vertex is the number of edges originating from or terminating at a given vertex. In other words, it is the number of edges of a graph incident with a given vertex.
For example,
An edge is incident to vertices and if for a graph where .
i.e., If is an edge connecting vertex and . Then and are incident to .
A complete graph with n vertices is denoted as and has edges.
For example: four-vertex complete graph is denoted as .
In conclusion, a complete graph:
- has no loops, i.e. ,
- has no parallel edges, i.e. ,
- ,
- has edges where n is the number of vertices in a graph.
Adjacency list for the above graph is:
Reference:
INTRODUCTION TO GRAPH THEORY BY ROBIN J WILSON
Wilson, R. J. (2015). Introduction to graph theory. Pearson Education Limited