Definitions

Wednesday, 24 April 2019

10:07 AM

Path - walk with no repeated edges

Circuit - closed path

 

Euler path; non-closed walk passing each edge once.

Euler circuit; closed walk passing each edge once.

 

Hamilton path; non-closed walk passing each vertex once.

Hamilton circuit closed walk passing each vertex once.

 

 

 

Euler circuit if and only if each vertex has an even degree

Euler path if and only if there are exactly 2 vertices with an odd degree

 

 

 

Euler circuit algorithm

• Set  for some vertex  in G
• Choose a circuit  with at least one vertex , but no edge, of
• Replace one of the 's in  by
• Continue the process until  contains all edges in

 

 

Dirac's Theorem

If  for all  then G has a Hamilton circuit

(If the condition does not hold true, it does not disprove that G is a Hamilton circuit)

 

Isomorphic - Same structure

 

A property of a graph  is an invariant. If  also has this property whenever

ie - number of vertices

ie - number of edges

ie - sum of degrees

ie - number of vertices of a given degree

ie - bipartiteness, connectedness