Question

Incidence matrix and Adjacency matrix of a graph will always have the same dimensions?
a) True
b) False

Answer 1

Hint: The size of the incidence matrix is equal to the number of vertices and the number of edges of the graph whereas the adjacency matrix depends on the labeling of vertices of the graph.

Complete step-by-step answer:
The Incidence Matrix of a Graph:
Let $G=(V,E)$be a graph where $V=\left\{ 1,2,......,n \right\}$ and $E=\left\{ {{e}_{1}},{{e}_{2}},....,{{e}_{m}} \right\}$. The incidence matrix of G is an $n\times m$ matrix $B=\left( {{b}_{ik}} \right)$, where each row corresponds to a vertex and each column corresponds to an edge such that if ${{e}_{k}}$ is an edge between i and j, then all elements of column k are 0, except ${{b}_{ik}}={{b}_{jk}}=1$

The Adjacency Matrix of a Graph:
Let $G=(V,E)$be a graph where $V=\left\{ 1,2,......,n \right\}$ and $E=\left\{ {{e}_{1}},{{e}_{2}},....,{{e}_{m}} \right\}$. The incidence matrix of G is an $n\times m$ matrix $A={{a}_{ij}}$, where ${{a}_{ij}}=1$ if there is an edge between vertex i and vertex j, else ${{a}_{ij}}=0$

Therefore, we conclude that the Incidence matrix and Adjacency matrix of a graph does not have the same dimensions.

So, the correct answer is “Option b”.

Note: An incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y.
An adjacency matrix is a square matrix utilized to describe a finite graph. The components of the matrix express whether the pairs of a finite set of vertices (also called nodes) are adjacent in the graph or not. Sometimes adjacency matrices are also called a vertex matrix.