Math & Comp Sci: Graph theory: what is an elementary subdivision?

The tutor shows the easy concept, from graph theory, of elementary subdivision.

An elementary subdivision on a graph replaces one edge by two, with a new vertex installed between them.

Consider the following two graphs:

Graph 1

Graph 2

Graph 2 is produced from Graph 1 by an elementary subdivision. First, edge DA is removed, then vertex P is added between D and A. Finally, edges DP and PA are drawn.

Elementary subdivisions are used to compare graphs for similarities.


Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. Don Mills: Addison-
  Wesley, 1994.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Tagged with: ,

Leave a Reply