Acyclic graphs and trees An acyclic graph is a graph with no cycles A tree is an acyclic connected graph Acyclic, unconnected clic, connected not tree not tree The number of arcs in a tree is always one less than the number of nodes Proof: start with arbitrary node and each time you add an arc you add a node =>N nodes and N-1 links. If you add an arc without adding a node, the arc must go to a node already in the tree and hence form a cycleAcyclic graphs and trees • An acyclic graph is a graph with no cycles. • A tree is an acyclic connected graph. 1 2 4 3 1 2 3 1 2 3 Acyclic, unconnected Cyclic, connected not tree not tree • The number of arcs in a tree is always one less than the number of nodes – Proof: start with arbitrary node and each time you add an arc you add a node => N nodes and N-1 links. If you add an arc without adding a node, the arc must go to a node already in the tree and hence form a cycle Eytan Modiano Slide 9