Trees and plane graphs
Recognise trees, count the edges of a tree and of a spanning tree, and count the faces of a plane graph with Euler's formula.
- Russia: grade 8
Guide
In the Russian Grade 8 programme (Probability and Statistics, graphs) a tree is a connected graph with no cycles. Properties: exactly one chain between any two vertices; a tree with n vertices has exactly n - 1 edges; a tree with more than one vertex has a leaf (a vertex of degree 1). Trees describe family trees, tables of contents and knock-out tournaments.
A spanning tree of a connected graph is a part that contains all vertices and is a tree. To get one from a graph with V vertices and E edges remove E - (V - 1) edges, one from each cycle.
A graph is plane (planar) if it can be drawn without crossing edges. For a connected plane graph Euler's formula holds: V - E + F = 2, with F the number of faces including the outer one. This is advanced material.