Graph Theory review notes.

Authors Avatar by davidwang101016 (student)

Graph theory review

Graph types

Simple: no loops or multiple edges

Complete: has every pair of vertices adjacent. One move can get you from one vertex to any other vertex. (n vertices--->Kn)

Connected: has every vertex accessible from every other vertex, but not necessarily directly.

Bipartite: has vertices in two sets and each edge joins one vertex from each set. Vertices within each set are not joined.

Complete Bipartite: has every vertex in one set joined to every other vertex in the other set (m vertices in one set, n vertices in the other--->Km,n)

Wheel: has every vertex connected to a central hub. (Wn)

Two graphs are isomorphic:

Equal size + Equal order + Same Degrees + Connectivity is preserved

Join now!

The complement of a graph will have all of the same vertices but its edges will be all of the possible edges that the original graph does NOT have.

Handshaking Lemma: For any graph G, the sum of degrees of the vertices in G is twice the size of G.

Pigeonhole Principle: n pigeons in m holes, and n>m, then there must be at least one hole containing more than one pigeon.

Planar graph: a graph without any edges crossing each other

For graph, G, to be planar: 

If G is a simple graph:

If G is a bipartite graph:

Any ...

This is a preview of the whole essay