Graph Theory Exam 2

Spanning tree

subgraph T of G which is a tree and for which V(T)=V(G)

weights or costs

assigned by certain numbers used for Kruskal’s algorithm and Prim’s algorithm

minimum spanning tree

for a graph G with weight function w is a spanning tree T of G for which w(T) is minimized

Kruskal’s algorithm

build it one edge at a time, start with F_0, the first one has no connections, cannot have a cycle, and go in order

Prim’s (Jarnik’s) algorithm

we use T_0 and so on, use an edge list, go in order, start with a certain vertex and add the edges, should be the same structure as Kruskal’s for the final result

Every connected graph contains a

spanning tree

Kruskal’s algorithm produces a minimum spanning tree in a

connected weighted graph

Prim’s algorithm produces a minimum spanning tree in a

connected weighted graph

cut-vertex

G-v has more components than G (you only cut one vertex)

Let v be a cut-vertex in a connected graph G and let u and w be vertices in distinct components of G-v

then v lies on every u-w path in G

A vertex v of a connected graph G is a cut vertex of G if and only if there exist

vertices u and w distinct from v such that v lies on every u-w path of G

Let G be a nontrivial connected graph and let u be in V(G). If v is a vertex that is farthest from u in G then

v is not a cut vertex of G

every nontrivial graph contains

at least two vertices that are not cut-vertices

non separable graph

nontrivial connected graph with no cut-vertices

block

a maximal non separable subgraph of G

a graph of order at least 3 is non separable if and only if

every two vertices lie on a common cycle

Let G be a nontrivial connected graph. Define the relation R on E(G) by

eRf if e=f or if e and f lie on a common cycle of G (R is an equivalence relation)

Every two distinct blocks B1 and B2 in a nontrivial connected graph G have the following properties

• the blocks B1 and B2 are edge-disjoint

• the blocks B1 and B2 have at most one vertex in common

• if B1 and B2 have a vertex in common then v is a cut vertex of G

vertex-cut

in a connected graph G is a set of vertices U for which the subgraph G-U is disconnected

vertex connectivity

denoted as k(G) known as kappa which is fancy k and k with the lines on the top and bottom going towards the left

minimum

a set S is minimum with property P for every other set T with property P, |S|≤|T|

minimal

property P if for every proper subset T of S, T does not have a property P

trivial graph

if a graph cannot be disconnected by deleting vertices its vertex connectivity is the number of vertices which must be deleted

G is k connected if

k(G)≥k (kappa of G)

edge cut

nontrivial connected graph is a set of edges X for which G-X is disconnected

edge connectivity

size of a minimum edge cut for a graph G (denoted as λ)

for every positive integer n

λ(K_n)=n-1

for every graph G

k(G)≤λ(G)≤δ(G) which means the vertex connectivity≤edge connectivity≤min degree

if G is a cubic graph

k(G) = λ(G)

if G is a graph of order n and size m≥n-1

k(G)≤[2m/n]

if G is a connected graph of order at least 3

then its square G² is 2-connected

Menger’s Theorem

a set of vertices S in a graph G is said to separate vertices u and v if G-S is disconnected and u and v lie in different components of G-S. Then S is a u-v separating set

Let u and v be nonadjacent vertices in a graph G

minimum number of vertices in a u-v separating set equals the maximum number of internally disjoint u-v paths in G

a nontrivial graph G is k-connected for some integer k≥2 if and only if

for each pair u,v of distinct vertices of G there are at least k internally disjoint u-v paths in G

Let G be a k-connected graph and let S be any set of k vertices

if a graph H is obtained from G by adding a new vertex w and joining w to the vertices of S, then H is also k-connected

Ig G is a k-connected graph and u,v1,v2,…,vk are k+1 distinct vertices of G

then there exist internally disjoint u-vi paths (1≤I≤k) in G

if G is a k-connected graph, k≥2 then

every k vertices of G lie on a common cycle of G

for distinct vertices u and v in a graph G the minimum number of edges of G that separate u and v

equals the maximum number of pairwise edge-disjoint u-v paths in G

a nontrivial graph G is k-edge connected if and only if

G contains k pairwise edge disjoint u-v paths for each pair u,v of distinct vertices of G

planar

if it can be drawn in R² with no edge crossings

faces

if G is planar and drawn without crossings we say G’s faces are the regions in R² bounded by the edges of G

outer face

the unbounded area outside of the drawing of G

minor

a graph H is a minor of G if H can be obtained from G by deleting edges, deleting vertices, or contracting edges

Wagner’s Theorem

a graph G is planar if and only if it does not contain k5 or K3,3 as a minor

Kuratowski’s Theorem

a finite graph is planar if and only if it does not contain a subdivision of K5 or K3,3

Möbius strip

top and bottom edges are distinct from each other (the left line goes up the right line goes down while the top and bottom line don’t move/do not exist)

Torus

left line goes up right line goes up and the top and bottom line go to the right

Klein bottle

left line goes up right line goes down top and bottom line go to the right

proper vertex coloring

C is a set of colors and c(u) does not equal c(v) for all uv in E(G) so each vertex is assigned one color and two adjacent vertices cannot have the same color

chromatic number

denoted as χ(G)

minimum vale of k such that G is k-colorable

Brook’s Theorem

Let G be a connected graph that is not a complete graph or an odd cycle then χ(G)≤Δ(G) (chromatic number ≤ max degree)

Four Color Theorem

every planar graph is 4-colorable χ(G)≤4 when G is planar

Euler’s Formula

Let G be a connected planar graph with v vertices, e edges, and f faces then v-e+f=2