discrete math 2 - chapter 13

undirected graph

the edges of this graph are unordered pairs of vertices. {a,b} = {b,a}

a graph is finite when…

the vertex set is finite

parallel edges

multiple edges between the same pair of vertices

self-loop

an edge bewteen a vertex and itself

simple graph

a graph that does not have parallel edges or self-loops

example of a directed edge

(a,b)

example of an undirected edge

{a,b}

adjacent definition

there is an edge between two vertices

neighbor definition

edge a is a neighbor to edge b if there is an existing edge between them

degree of a vertex

the number of neighbors a given vertex has

total degree

the sum of the degrees of all of the vertices. is equal to the number of edges present multiplied by 2

in a regular graph, all of the vertices have the same degree. In a d-regular graph, all the vertices…

..have a degree of d

graph A is a subgraph of graph B if…

both the vertices and edges in graph A are subsets(aka present) of graph B

Theorem: Number of edges and total degree

twice the number of edges in any undirected graph is equal to the total degree.

deg(v) = 2 x |E|

Kn

• the complete graph on n vertices.

• Kn has an edge between EVERY pair of vertices

• sometimes called a clique of size n or an n-clique

Cn

• called a cycle of n vertices

• edges connect in a ring

• Cn is well defined only for n being greater than or equal to three

Kn,m

• has n+m vertices

• no edges between vertices of the same set

• an edge between every vertex in one set and every vertex in another set

two graphs are isomorphic if…

there is a correspondence between the vertex sets of each graph, such that there is an edge between two vertices of one graph IAOI there is an edge between the corresponding vertices of the second graph.

Basically, two graphs are isomorphic if

• they have the same number of edges

• they have the same number of vertices

• they have the same degree

degree sequence

the list of the degrees of all of the vertices in non-increasing order.

ex: 4,3,3,3,2,1

one vertex of degree 4, 3 vertices of degree 3, one vertex of degree 2, and one vertex of degree 1

bijection rule

if there is a bijection from one set to another, then the two sets have the same cardinality

Let S and T be two finite sets. If tehre is a bijection from S to T, then |S| = |T|

a function f from set S to set T is called a bijection IAOI…

it has a well defined inverse