page2
procedure Euler(G: multigraph...)
pick a vertex, say a
circuit := pick any circuit in G that starts at a
H := G with the edges of the circuit removed
while H has edges
subcircuit := a circuit in H beginning at a vertex in H that
also is an endpoint of an edge of the circuit.
H := H with edges of subcircuit and all isolated vertices removed
circuit := circuit with subcircuit inserted at the appropriate
vertex
return circuit {circuit is an Euler circuit}
procedure Dijkstra(G: weighted connected simple graph, with all weights positive)
{G=(V,E) has vertices a = v0, …, vn = z, and weights w(vi,vj), where w(vi,vj) =  if {vi,vj}  E}
for i:= 1 to n // set all the labels to infinity
L(vi) := 
L(a) := 0, S :=  // set a's label to 0 and set S is empty infinity
while z  S
u := a vertex not in S with smallest L(u)
S := S  {u} // adding a vertex to S
for all vertices v not in S // update the labels; vertices are adjacent to u
if L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v)
return L(z) // return the length of a shortest path from a to z
[Def] a graph is called planar if it can be drawn in the plane without edges crossing.
Such a drawing is called a planar representation of the graph.
[Def] A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
[Def] A chromatic number of a graph is the least number of colors needed for coloring of this graph.
denotation: (G)
[Theorem] The Four Color Theorem
The chromatic number of a planar graph is no greater than four.
[Theorem] Number of edges in a planar graph
Consider a connected planar simple graph G=(V,E), where |V| = n, |E| = m with n ≥ 3, then
m ≤ 3n − 6
[Theorem 2] Number of edges in a planar graph
If a connected planar simple graph G=(V,E) has n vertices with n ≥ 3 and m edges and no circuits of length three, then m ≤ 2n − 4