Graph Theory Exam 1

Order of a graph

Number of vertices

Size of a graph

Number of edges

Trivial Graph

Specific type of empty graph where G=(V,E) or E = empty set

Empty Graph

G=(V,E) where |v| ≥ 1, E = empty set

Equal Graphs

Two graphs might be equal which means they are labeled

Proper subgraph

If H subset G such that H does not equal G, then H is a proper subgraph of G

Spanning subgraph

If V(H) = V(G) and E(H) is a subset of E(G) then H is a spanning subgraph

A subgraph H spans G

if it uses all the vertices of G

Induced subgraph

A subset V’ is a subset of V(G) on V’ is the graph H with vertex set V’ = V(H) and all edges in G supported on these vertices

u-v Walk

a series of adjacent vertices and edges starting with u and ending with v

u-v Trail

u-v walk where we can’t repeat edges

u-v Path

u-v trail which does not repeat vertices which also means it can’t repeat edges

u-v walk/trail/path is closed

u=v

closed trail

circuit (no repeated edges)

closed path

cycle (no repeated vertices so no repeated edges)

A graph G is connected

if and only if for all u,v in V(G) there exists a u-v path in G

Connected component of a graph G

maximal connected subgraph H of G

if you have a u-v walk

you have a u-v path

u-v Geodesic

shortest u-v path

a graph G contains a u-v walk of length l

then G contains a u-v path of length ≤ l

Let R be the relation defined on the vertex set of a graph G by u R v where u,v in V(G)

if u is connected to v that is G contains a u-v path

Let G be graph of order 3 or more. If G contains two distinct vertices u and v such that

G-u and G-v are connected then G itself is connected

If G is a connected graph of order 3 or more

then G contains two distinct vertices u and v such that G-u and G-v are connected

Let G be a graph of order 3 or more then G is connected

if and only if G contains two distinct vertices u and v such that G-u and G-v are connected

graph operations

complement, join (G+H), and Cartesian product

cycles

C_n

complete graphs

K_n

empty graph

K bar_n

Star graph

K_1,s

bipartite graph

v_1 and v_2 are partite sets (no edges within a partite set)

multipartite graph

K-partite graph

complete bipartite

K_s,t

complete k-partite graph

K_n_1,n_2,n_3,..,n_k

hypercube

Q_n is hypercube of dimension n

Q_n

vertices is set of binary n-tuples, 2 vertices are neighbors if their n-tuples differ in exactly one position 

If G is a disconnected graph

G bar is connected

Nontrivial graph G is bipartite graph if and only if

G contains no odd cycles

multigraph

graph which there may be more than one edge connecting a pair of vertices (parallel edges)

pseudo graph

multigraph which edge can start and end at the same vertex (loops)

digraph

edges are ordered pairs of vertices (directed edges or arcs)

oriented graph

digraph for which at most one of (u,v) and (v,u) is an edge for each pair of vertices u,v

orientation of K_n

tournament

hypergraph

graph whose edges can consist of more or less than two vertices (hyper edges)

a leaf has one

neighborhood

neighborhood

the vertices that is connected to that point

First theorem of graph theory

if G os a graph of size m, then the sum of v in V(G) deg v = 2m (sum of all degrees equals twice the number of edges)

every graph has an even number of

odd vertices

Let G be a graph of order n. If deg u + deg v ≥ n-1 for every two nonadjacent vertices u and v of G 

then G is connected and diam(G)≤2

a graph is regular if 

all of its vertices have the same degree

r-regular graph

shared degree is r

Peterson graph

famous cubic graph

degree sequence

list of degrees in a sequence

if there exists a graph with degree sequence s

s is graphical

Havel-Hakimi Theorem

cross out the largest number and use the number you crossed out to keep proving if it is graphical

bridge

an edge e for which G-e has more components than G

An edge e of a graph G is a bridge if and only

e lies on no cycle of G

acyclic 

a graph G does not contain a cycle as a subgraph, we call G a cyclic 

tree

connected acyclic graph

forest

disconnected acyclic graph

types of tree names

star, double star, caterpillar

a graph G is a tree if and only if

every two vertices of G are connected by a unique path

every nontrivial tree has at least

two end vertices

every tree of order n has size

n-1

every forest of order n with k components has size

n-k

the size of every connected graph of order n is at least

n-1

Let G be a graph of order n and size m. If G satisfies any two of the properties

(1) G is connected

(2) G is acyclic

(3) m=n-1

then G is a tree

Let T be a tree of order k. If G is a graph with min degree of G ≥ k-1 

then T is isomorphic to some subgraph of G