# Questions tagged [graph-connectivity]

For questions related to the vertex-connectivity or edge-connectivity of graphs or networks: the minimum number of vertices (respectively edges) that need to be deleted to disconnect the graph.

389 questions
Filter by
Sorted by
Tagged with
55 views

### Confusion regarding this definition of a connected graph

I have the following definition of a graph. Let $M \subset \mathbb{N}$ be a set of vertices and consider the set: $$\mathcal{G}(M) = \mathbb{P}(\{(n,m) \in M \times M: \hspace{0.1cm} n < m \})$$ ...
• 1,873
22 views

### Prove correctedness of connectivity of a K(n, 2) Kneser Graph

Is there any way to prove that given $n\neq4$, a $K(n, 2)$ Kneser Graph is connected if any two vertices in the graph either have a common neighbor or are adjacent to each other? I noticed that K(4,2) ...
31 views

### Proving that $\kappa'(G) - 1 \leq \kappa'(G - v)$.

I am studying graph connectivity and need to prove the following inequality involving vertex connectivity: $\kappa'(G) - 1 \leq \kappa'(G - v)$ I need to show that removing a vertex 𝑣 from a graph 𝐺...
66 views

### Let $G$ be a simple graph such that $\chi(G) = k$ and $\chi(G\setminus\{v\}) < k$ hold for all $v \in G$. Show that $G$ is 2-connected

I've been attempting to solve the following problem but I'm stuck. Let $G$ be a simple graph with at least 3 vertices such that $\chi(G) = k$ and $\chi(G\setminus\{v\}) < k$ hold for all $v \in G$. ...
• 33
73 views

### Connectivity of intersection graph

Let $\mathcal{F}$ be a family of $N$ finite subsets of $S=\{1, \dots, N\}$, each of size $k$ and $\bigcup \mathcal{F} = S$, and let $G=(\mathcal{F}, E)$ be the intersection graph of $\mathcal{F}$ (i.e....
19 views

### Number of 2-connected components in an almost 2-regular 3-uniform hypergraph

Notation: $[n]:=\{1,\ldots, n\}$, and $\binom{[n]}{k} := \{A \in 2^{[n]}\mid |A| = k\}$ for $k \in [n]$. Let $M$ be a perfect matching on an even number of vertices $n$, and let $\mathbb{S}_n$ be the ...
• 479
31 views

### The impact of removing an edge on the connectivity of these graphs.

The vertex connectivity $\kappa(G)$ of a graph G, also called connectivity, is the minimum size of a vertex cut. $G-xy$ is a graph obtained by removing an edge $xy$ from $G$. We can easily prove the ...
• 2,504
36 views

### Does there exist a 5-connected planar graph that is perfect?

In a previous post, I proved that no 5-connected maximal planar graph is perfect. My proof, with slight modifications, can show that if a maximal planar graph with minimum degree 5 is perfect, then ...
• 2,504
1 vote
62 views

### G a connected Graph. (Dis)Prove the following statement

The number $s(G)$ is the largest natural number $k$ for which there exists a clique $X \subseteq V(G)$ in the graph $G$ with $|X| = k.$ The number $c(G)$ is the smallest natural number $k > 2$ for ...
1 vote
22 views

### Conditions under which a non-doubly connected graph $G$ becomes doubly connected when a suitable edge is added?

What are the conditions under which a non-doubly connected graph $G$ becomes doubly connected when a suitable edge is added? I thought about this problem and was able to set some conditions for this ...
• 573
92 views

### Does there exist a 5-connected maximal planar graph that is perfect?

A graph $G$ is said to be perfect if $\chi(H)=\omega(H)$ hold for any induced subgraph $H_i\subseteq G$ (and so for $G$ itself, too) For maximal planar graphs with connectivity 3, it is easy to ...
• 2,504