# Distinguish Graph from Tree using Adjacency Matrix

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle).

For example, given the adjacency matrix:

0 1 0 1
1 0 0 1
0 0 0 1
1 1 1 0


This is not a tree since there is a cycle between Vertex 1, Vertex 2 and Vertex 4.

0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 0


This is a tree since there is no cycle.

One way to approach this is to perform a BFS but I think there might be a visual difference between an adjacency matrix of a graph and of a tree.

Any help would be appreciated!

• If we know it is connected then count number of edges in the graph. It will be tree iff n-1 edges are there. Otherwise, First check if it is connected. If not clearly not a tree. – Root Mar 20 at 19:12
• @Root how would we check if it is connected through code? – stuckyp Mar 20 at 23:45

I believe the easiest method is to first check if the number of vertices and edges align with $$m = n - 1$$ (if they don't definitely not a tree). Now we conclude either our graph is a tree or is disconnected but contains a cycle. So either we look for a cycle or look for connectivity, both methods are equivalent. To check for cycles, the most efficient method is to run DFS and check for back-edges, and either DFS or BFS can provide a statement for connectivity (assuming the graph is undirected).