Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 04 Trees
Tags: examplesSwitchExample1 hasSeenConjDef

Name: A tree
Definition: connected acyclic
Page: 99, 100
Chapter: 4
Section: 1
Index: 1, 3
Kind: Prop, Theo
Definition2: such that there exists one path between each pair of vertices
Conjdef: A graph \(G\), such that equivalently
Definition3: connected such that \(e(G)=v(G)-1\)

Name: A forest
Definition: An acyclic graph
Page: 99
Chapter: 4
Section: 1

Definition: The only path from \(x\) to \(y\)
Page: 99
Chapter: 4
Section: 1
Variables: \(T=(G,E)\) a tree,
\(x,y\in G\)
Notation: \(xTy\)

Name: A leaf
Definition: A vertex of degree one
Page: 99
Chapter: 4
Section: 1
Variables: \(T=(G,E)\) a tree,

Question: The number of leaves is
Answer: at least 2
Page: 99
Chapter: 4
Section: 1
Variables: \(T=(G,E)\) a tree,
Index: 2
Kind: Prop

Smaller0: \(e(G)\)
Greater0: \(v(G)\)
Page: 99
Chapter: 4
Section: 1
Variables: \((G,E)\) a graph,
Smaller to greater: +1=
Assuming: \(G\) a tree
Greater to smaller: =1+