Graph Theory

Adjacent

When two edges share a vertex, when 2 vertices share an edge

Loop

An edge that starts and ends on the same vertex (an edge with only 1 vertex)

Simple graph

A graph with no loops or multiple edges between the same two vertices

Degree

the number of edges incident to a vertex in a graph. A loop contributes 2 to the degree of an edge

Path

A sequence of adjacent edges & vertices traversed to get from one vertex to another w/o repeating an edge/vertex

Circuit

Path that starts and ends on the same vertex

Cut edge (also known as a bridge)

An edge that disconnects the graph when removed

Cut vertex

A vertex that disconnects the graph when it and all adjacent edges are removed

Walk

A way of getting from one vertex to another. EX: Vertex P —> Vertex R. A walk w/a length of 2. A walk where a vertex appears only once is a path.

Complete Bipartite Graph

A simple grapth w/2 sets of vertices such that every vertex in one set is connected to every vertex in the other set.

How do you know if complete bipartite graph has an Euler Path

A complete bipartite graph has an Euler path if and only if it has at most two vertices of odd degree. In general, for a graph to have an Euler path, it must either have zero or two vertices with odd degrees.

How do you know if a complete bipartite grapth has a Euler circuit

A complete bipartite graph has an Euler circuit if and only if all vertices have even degree. This means that every vertex must be connected to an even number of edges. (Both n and m must be even #s)

How to find the # of edges on a complete bipartite graph

M * N

Complete graph

Simple grapth w/ N vertices where each vertex is adjacent to every other vertex

How to know how many Hamiltonian paths/circuits on a complete graph?

N! (if N = 5, then 5 ×4×3×2×1, or if N=7, 7×6×5×4×3×2×1)

When can a complete graph have a Euler circuit

If N is odd because then every vertex has an even degree.

Tree

A connected graph w/no circuits. if a disconnected graph has no circuits, each connected component is a tree, thus creating a forest

How many edges does a complete graph have?

N(N-1)/2

How many edges will a tree have, if it has N vertices

N-1= Edges

What are vertices in a tree graph with a degree of 1 called?

Leaves, all other vertices are called branches

Complete binary tree

Number of leaves = 2ˆn, #of Branches (2ˆn)-1, Total # of vertices: (2ˆ(n+1) )-1