In a complete undirected graph with five vertices how many cells will contain a value of 1 in an adjacency matrix?
A) 15
B) 10
C) 25
D) 125

Question

Quizplus · Accepted Answer

In a complete undirected graph with n vertices, each vertex is connected to n-1 other vertices, which results in (n*(n-1))/2 total edges. In this case, n=5, so there are (5*(5-1))/2 = 10 edges in the graph. Each edge corresponds to a cell in the adjacency matrix, and since the graph is undirected, each edge corresponds to both a row and a column in the matrix. Therefore, there are a total of 2*10 = <<2*10=20>>20 cells in the matrix that contain a 1. However, each diagonal entry of the matrix corresponds to a vertex that is connected to itself, and since the graph is undirected, each such entry appears twice in the matrix. Therefore, we must subtract 5 (the number of diagonal entries) from the total count to get the final answer of 20 - 5 = <<20-5=15>>15 cells containing a 1 in the adjacency matrix.

In a Complete Undirected Graph with Five Vertices How Many