Maths(三)---Graphs and Trees(6)

Let G be a simple graph with n vertices, where n ≥ 3.

deg v + deg w ≥ n,

for each pair of non-adjacent vertices v and w, then G is Hamiltonian.

For figure 3.32, n = 5 but deg u = 2, so Dirac’s theorem does not apply.However, deg v + deg w ≥ 5 for all pairs of non-adjacent vertices v and w, so thisgraph is Hamiltonian by Ore’s theorem.

............................................................................................

Trees

A tree is a connected graph which contains no cycles.

􀂅 T is connected and has n − 1 edges.

􀂅 T has n − 1 edges and contains no cycles.

􀂅 T is connected and each edge is a bridge.

􀂅 Any two vertices of T are connected by exactly one path.

􀂅 T contains on cycles, but the addition of any new edges creates exactly onecycle.

Spanning Trees

Let G be a connected graph. A spanning tree in G is a subgraph of G that includesall the vertices of G and is also a tree. The edges of the tree are called branches.