Question

Use the Table button in the Rich-Text Editor to provide an adjacency matrix for a simple graph that meets the following requirements:

1) has 5 vertices
2) is maximal planar

Answer 1

Maximal Planar Graph:

A maximal planar graph is a planar graph to which no new edges can be added without violating planarity.

i.e. A planar graph is called maximal planar graph if adding an edge between any two non-adjacent vertices results in a non-planar graph.

Adjacency Matrix:

Let G be a graph with p vertices listed as . The adjacency matrix of G with respect to this particular listing of P vertices of G is matrix

where is number of edges joining vertex to

In case of simple graph the adjacency matrix

where

Following is the graph satisfying the given requirements.

Above graph is a maximal planar graph because if we add edge then it results in non-planarity of a graph.

Now we will calculate its adjacency matrix.

Procedure is explained below and then the matrix is given:

Rows are the vertices v₁, v₂, v₃, v₄ and v₅

and columns are the vertices v₁, v₂, v₃, v₄ and v₅

As v₁ is adjacent to all the remaining vertices v₂, v₃, v₄ and v₅

Hence entries in first column and first row is 1 everywhere except at v₁v₁ because v₁ is not adjacent to v₁

As v₂ is adjacent to vertices v₁, v₃ and v₄

Hence entries in second column and second row is 1 everywhere except at v₂v₂ and v₂v₅ and v₅v₂ because v₂ is not adjacent to v₂ and also not adjacent to v₅

As v₃ is adjacent to all the vertices v₁, v₂ ,v₄ and v₅

Hence entries in third column and third row is 1 everywhere except at v₃v₃ because v₃ is not adjacent to v₃

As v₄ is adjacent to all the vertices v₁, v₂ ,v₃ and v₅

Hence entries in fourth column and fourth row is 1 everywhere except at v₄v₄ because v₄ is not adjacent to v₄

As v₅ is adjacent to vertices v₁, v₃ and v₄

Hence entries in fifth column and fifth row is 1 everywhere except at v₅v₅ and v₂v₅ and v₅v₂ because v₅ is not adjacent to v₂ and also not adjacent to v₅

	v1	v2	v3	v4	v5
v1	0	1	1	1	1
v2	1	0	1	1	0
v3	1	1	0	1	1
v4	1	1	1	0	1
v5	1	0	1	1	0

Thus above is the adjacency matrix for the graph.