[prev] 17 [next]

Graph Terminology (cont)

Tree: connected (sub)graph with no cycles

Spanning tree: tree containing all vertices

n-Clique: complete subgraph on n nodes

Consider the following single graph:

[Diagram:Pic/graph2.png]

This graph has 26 vertices, 33 edges, and 4 connected components

Note: The entire graph has no spanning tree; what is shown in green is a spanning tree of the third connected component