Question

Discrete math

Summarize all the theorem regarding to graph theory.

e.g.) A connected graph has a Euler circuit iif every vertex is of even degree.

Answer 1

 

Euler Theorem: A connected graph G=(V,E) is considered Eulerian if and only if all vertices in V(G) have an even degree, otherwise the graph is not Eulerian.

Diraces Thm: If G=(V,E) is a connected graph on n-vertices so that for every x,y∈V(G) where x≠y, the deg(x)+deg(y)≥n for all x and y, then G is Hamiltonian.

Ore's Theorem: If G=(V,E) is a connected graph on n-vertices so that for every x,y∈V(G) where x≠y, the deg(x)+deg(y)≥n for all pairs of x and y that are adjacent, then G is Hamiltonian.

Theorem: If a graph G has 2m odd vertices, then the graph can be drawn in precisely m strokes.

Cayley's Theorem: For n≥1, there are precisely nn−2 tree graphs on n-labelled vertices.

Kuratwoski's Theorem: A graph G is planar if it does not contain any subdivisions of K5 or K3,3.

Brooke's Theorem: If G is a connected simple graph, and is not a complete graph or a cycle graph with an odd number of vertices, then the chromatic number χ(G)≤Δ(G).

Vizing's Theorem: For any graph, Δ(G)≤χ′(G)≤Δ(G)+1.