TREES

 A tree is a connected graph without any circuits

 Trees with one, two, three, and four vertices are shown below

null tree, a tree without any vertices

THEOREM 1 There is one and only one path between every pair of vertices in a tree, T.

 Proof:

Since T is a connected graph, there must exist at least one path between every pair of vertices in T. Now suppose that between two vertices a and b of T there are two distinct paths. The union of these two paths will contain a circuit and T cannot be a tree.

THEOREM 2 : If in a graph G there is one and only one path between every pair of vertices, G is a tree.

Proof:

Existence of a path between every pair of vertices assures that G is connected. A circuit in a graph (with two or more vertices) implies that there is at least one pair of vertices a, b such that there are two distinct paths between a and b. Since G has one and only one path between every pair of vertices, G can have no circuit. Therefore, G is a tree.

A tree T is said to be a spanning tree of a connected graph G if T is a subgraph of G and T contains all vertices of G.

ADJACENCY MATRIX

The adjacency matrix of a graph G with n vertices and no parallel edges is an n by n symmetric binary matrix X = [xij ] defined over the ring of integers such that

xij = 1, if there is an edge between ith and jth vertices, and

      = 0, if there is no edge between them.

Q: Draw the adjacency matrix of the given graph

Ans: The adjacency matrix is