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

Eulerian Graphs

A connected graph G is Eulerian if there is a closed path which includes every edgeof G; such path is called an Eulerian path.

Let G be a connected graph. Then G is Eulerian if and only if every vertex of G has even degree.

例一.

Which graph(s) is/are Eulerian?

Answer: Graph (a) and (b) are Eulerian

Hamiltonian Graphs

A connected graph G is Hamiltonian if there is a cycle which includes every vertexof G; such a cycle is called a Hamiltonian cycle

Let G be a simple graph with n vertices, where n ≥ 3. If deg v ≥ 21 n for eachvertex v, then G is Hamiltonian.

For the above graph, n = 6 and deg v = 3 for each vertex v, so this graph isHamitonian by Dirac’s theorem.