Connectivity

Question 1

When is a graph G connected?

Answer 1

If there exists a u-v path between all vertices in G

Question 2

What is an AB-path in G?

Answer 2

Two subsets of vertices A and B in G, which consists of paths in G with 1 endpoint in A and 1 endpoint in B

Question 3

What is an AB-separator, S? And what is s(G,A,B)?

Answer 3

S is a set of vertices in which every AB-path goes through S. s(G,A,B) is the minimum number of vertices in an AB-separator, S.

Question 4

State: Menger’s Theorem-Vertex Version

Answer 4

For every graph G and for all A,B in V(G) there is a set of s(G,A,B) disjoint AB-paths in G

Question 5

What does it mean for two vw-paths to be internally disjoint?

Answer 5

It means they have no common vertices other than v and w

Question 6

State: Menger’s Theorem-Local Vertex Version

Answer 6

For distinct vertices v, w in a graph G, there are t(G,v,w) internally disjoint paths between v a w.

Question 7

When is a graph G k-connected?

Answer 7

If G has more than k vertices and every cutset has size at least k

Question 8

What is the connectivity of G, kappa(G)?

Answer 8

The maximum k such that that G is k-connected. Or it is the size of the smallest cutset.

Question 9

State Menger’s Theorem - Global Vertex Version

Answer 9

for k at least 1 a graph G is k-connected iff for each pair of distinct vertices, there are k internally disjoint path between them

Question 10

Mader’s Theorem: For every integer k at least 1, every graph G with average degree d(G) at least 4k contains a ___-connected subgraph H with minimum degree delta(G) at least ___ and average degree d(H) \geq ___ \geq ___

Answer 10

(k+1)… 2k+1… d(G) - 2k… 2k

Question 11

What is an edge-cutset U of E(G)?

Answer 11

A subset of the edge set of G, U of E(G), such that G-U is disconnected.

Question 12

When is G edge k-connected?

Answer 12

if |V(G)| \geq 2 and ever cutset has size at least kW

Question 13

What is the edge-connectivity of a graph G with |V(G)| \geq 2 deonted lambda(G)?

Answer 13

The maximum integer k such that G is edge-connected or it is the size of the smallest edge-cutset.

Question 14

Vertex connectivity of (G) \leq edge connectivity (G) \leq minimum degree of (G)

Answer 14

kappa(G) \leq lambda(G) \leq delta(G)

Question 15

When are two u-v paths edge-disjoint? And what is t(G,u,v)?

Answer 15

If they share no edges in common. The minimum number of edge whose deletion destroys all u-v paths in G

Question 16

State Menger’s Theorem-Local Edge Version

Answer 16

For distinct vertices u,v in a graph G, the maximum number of edge-disjoint uv paths in G equals t(G,u,v)

Question 17

State Menger’s Theorem-Local Edge Version

Answer 17

For every graph G and integer k \geq 1, G is k edge-connected iff for each pair of vertices, there are at least k edge disjoint paths between them.