1. Home
  2. Docs
  3. Discrete Structure
  4. Graphs
  5. Special Types of Graph

Special Types of Graph

  • Trivial Graph
  • Complete Graph
  • Regular Graph
  • Bipartite Graph
  • Complete Bipartite Graph
  • Cycle Graph
  • Wheel Graph
  • Platonic Graph

‣ Trivial Graph:

A trivial graph is a graph with only one vertex and no edges. It is the simplest possible graph.


image 107

‣ Complete Graph:

A graph G is said to be complete if there exists exactly one edge between any pair of vertices in G.

• The complete graph with n vertices is denoted by kn.

image 100

‣ Regular Graph:

A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of degree r, the degree of each vertex of G is r.

image 100

• In above figure, k2, k3, k4, k5, k6, k7 are 2-regular,

‣ Bipartite Graph:

A bipartite graph is a graph in which the vertices can be divided into two sets, such that every edge connects a vertex in one set to a vertex in the other set.

image 101

• In above figure, bipartite sets are: {1,2,3,4,5} and {A,B,C,D,E}

‣ Complete Bipartite Graph:

A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to every single vertex in the second set. The complete bipartite graph is denoted by Km,n where the graph G contains m vertices in the first set and x vertices in the second set.

image 102

‣ Cycle Graph:

A cycle graph is a graph that consists of a single cycle. In other words, it is a graph in which every vertex is connected to exactly two other vertices, and there are no edges that connect vertices that are already connected by another edge.

image 104

• Each vertex in the above figure is connected to exactly two other vertices by edges.

‣ Wheel Graph:

A wheel graph is a graph that consists of a single vertex connected to all other vertices in the graph by an edge. The other vertices in the graph are called the rim of the wheel.

image 105

• The vertex in the center of the diagram is the hub of the wheel, and the other vertices are the rim of the wheel.

‣ Platonic Graph:

The graph formed by the vertices and edges of five regular platonic– the tetrahedron, octahedron, cube, dodecahedron, and icosahedron are called the platonic graphs.

image 106

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *