Graph Theory

Hamiltonian Cycle

every vertex used once and returns to the start

Hamiltonian Path

-every vertex used exactly once
-simple path by default

Eulerian Path/cycle

-every edge is used once, vertices can repeat
Traits: every vertex has an even degree, graph is connected

Simple Path

-Path does not repeat a vertex (except at start if cycle)
-Does not have to visit every vertex

Hamiltonian and Bipartite Theorem

|A| and |B| are sets from a bipartite graph:
if |A| and |B| do not equal each other, then NOT Hamiltonian
if the difference between A and B >1, then there are NO Hamiltonian Paths
does not confirm if Hamiltonian is else

Bipartite Graph max edges

n/2 x n/2

Bipartite Theorem

An undirected graph bipartite only if it has NO odd length cycles

Bipartite graphs

-can split vertices into 2 distinct groups that do not have edges inside groups
- cannot have an odd cycle length

Tournamnt Graphs

-every player (dot), plays every other player (no ties exist)
-Every tournament has exactly on direct edge between every pair

- for every pair of distinct vertices u and v, exactly one of (u,v) or (v,u) is an edge.

Complete Graphs K_n

-every pair of vertices is connected
-max number edges: n*(n-1)/2

Complete Bipartite Graphs

-Bipartite graph where all vertices of one side connect to the other

Hamiltonian Bipartite graphs

The number of A and B set vertices must be the same, NOT Hamiltonian graph

and the difference cannot be greater than one No Hamiltonian Path

Tournament Theorem

Every tournament has a hamiltonian path but not always a Hamiltonian cycle

Complete Bipartite Graphs

every pair of vertices are connection
max number of edges is n(n-1)/2

Tournament Graphs

always a directed graph where there is no overlap
n(n-1)/2 total number of edges

Proof By contradiction

d espeucally for gaph isomorihism
-Assue false taht the outdgree

Isomorphism

-Same number of edges, and vertices

-use proof by contradiction, higher

Handshaking Lemmaa

Given a number of vertices, the summation of all degrees is 2(e), same degree sequence

Hamiltonian Paths in Tournaments PRoccess

pick a vertex a₁, find the in-vertx to a₁, put at the front of the set, and add teh others in between

Star Theorem

any vertex max out degree is a star, find vertex at max out

Havel-Hakimi Theorem

d = (d1,d2,dn) in a non deccreasing order, d is graphic if d’ = (d2—1,d3….)

Havel-Hakimi Process

sort, remove first number x, and reduce x numbers by one.
repeat until everything equals 0 or hit a (-) number