discrete connectivity

separating set

any subset of vertices S such that G\S is disconnected or G\S consists of onevertex

vertex connectivity

minimum cardinality of separating set of vertices

k(G)

vertex connectivity

δ(G)

minimum degree of G

relation between k(G) and δ(G)

k(G) <= δ(G)

k-connected

a graph is called k connected if k(G) >= k . removing (k-1) vertices from a graph will not disconnect the graph

T/F 1-connected —> 2-connected

False

T/F 2-connected —> 1-connected

True

k(G) for G= P_n (path)

k(P_n)=1

k(G) for G=K_n (Complete graph)

k(K_n)= n-1

k(G) for G= K_m,n (bipartite)

k(G) = min(m,n)

k(G) for G= petersen

k(petersen) = 3

disconnecting set of edges

a subset f is called disconnecting set of edges if removing edges in F disconnects G

edge connectivity

minimum size of a disconnecting set of edges

λ(G)

edge connectivity

λ(G) for complete graph

n-1

T/F k(G) = λ(G)?

False

T/F for complete graphs, k(G) = λ(G)?

True, n-1

T/F for cycles, k(G) = λ(G)?

True

edge cut

an edge set that disconnects the graph

relationship between k(G) and δ(G)

k(G) <= δ(G)

relationship between λ(G) and δ(G)

λ(G) <= δ(G)

relationship between k(G), λ(G), and δ(G)

k(G) <= λ(G) <= δ(G)

cut set

minimal set of edges whose removal disconnects graph

3 regular graph

every vertex has degree 3

relationship between k(G) and λ(G) for 3-regular graph

λ(G) = k(G)

internally disjoint

2 paths P,Q are internally disjoint if no vertices in P and Q apart from u and v are common

when is graph 2-connected if |V(G)| >= 3

there exist 2 internally disjoint u,v paths in G for all u,v in V(G)