# 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.

165 questions
Filter by
Sorted by
Tagged with
18 views

### Proof check : In a connected simple undirected graph with degree of each vertex greater than $1$ there exists a cycle

Question : Let $G\left( V,E\right)$ be a connected simple undirected graph such that $deg\left( v\right) \geq 2\forall v\in V$ , then there exists a simple circuit in $G$ We start by removing ...
20 views

31 views

24 views

### Maximum set of edges or vertices that doesn't disconnect graph

A graph is k-connected if every set of fewer than k vertices does not disconnect the graph, and a graph is k-edge-connected if every set of fewer than k edges does not disconnect the graph. The ...
53 views

### 3 connected graphs

I am trying to understand the following Lemma: Let G be a 3 connected graph of order at lest five and x in V(G). Suppose degree of x in G is 3 and the set of vertices adjacent to x in G is {a,b,c}. If ...
55 views

### $k$-connectivity graph partitions

What is the right definition to generalise the following observations? 1. $1$-connectivity induces a partition of graph vertices into $1$-connected components 2. $2$-connectivity induces a partition ...
51 views

### With reference to an argument related to a spanning path in a connected $4$-regular graph

I have a 4-regular odd ordered connected graph, say $X$. It is a vertex transitive graph, so there exists a perfect matching for the graph $X-v$, for any vertex $v \in X$. There I consider two ...
73 views

### Proving that articulation points lay on all paths between two vertices

Let $G = (V, E)$ be a simple connected undirected graph with $z \in V$. How can I prove the following claim. The vertex $z$ is an articulation point in $G$ if and only if there exists to distinct ...
67 views

### vertex connectivity proof

I was going through a graph theory book and found this Let $G$ be a simple undirected graph. $\kappa(G) <\frac{n}{2}$ . If $G$ is connected, then $G$ must contain a simple path of length at least ...
26 views

### Does a $k$-connected graph has $k$ totally disjoint $S-T$ paths for $|S|=|T|=k$?

I read about the question here: Prove that $G$ has $k$ pairwise disjoint $S$,$T,$ Paths? And I am interested in whether the result still holds for $S\cap T\neq \emptyset$. So the problem is: ...
45 views

### Is this an equivalent definition for connectivity in graphs?

Let $G=(V,E)$ be a simple graph. The usual definition of connectivity is: $G$ is connected iff for each pair of vertices $u,v\in V$, there exists a path between $u$ and $v$. I am fine with this ...
180 views

25 views

### Graphs “weak” in context of cutting subgraphs

This is an updated cross-post from MO: https://mathoverflow.net/questions/340215/graphs-weak-in-context-of-cutting-subgraphs where it didn't get much attention. Lately we've been looking into graphs (...
58 views

### Edge connectivity of bipartite subgraph.

Let G be a (2k-1)-edge connected multigraph. Show that G has a k-edge connected bipartite subgraph. I try to consider an induced bipartite subgraph H with maximum edge-connectivity t, and do an ...
159 views

### Maximum number of edges in minimally $k$-edge-connected multigraph

A graph or multigraph is $k$-edge-connected if it cannot be disconnected by deleting fewer than $k$ edges. It is minimally $k$-edge-connected if it loses this property when any edges are deleted. (...
49 views

### Polyamory Network problem

Two Related Problems: 1. Imagine polyamorous people form a complicated network. Define each person as a unique node. Define a relationship between two people as an edge. Each node can possibly ...
143 views

### Number of edges in a minimal $k$-edge connected subgraph

We know that any minimal connected subgraph of a connected graph with $n$ nodes has exactly $n-1$ edges. What are the known bounds (especially upper bounds) for the number of edges in a minimal $k$-...
40 views

### If Degree of a Vertex Greater Than/Equal to Size of Vertex Set / 2 then Connected

I encountered a question asking to prove that if the degree of every vertex is greater than or equal to the floor of the size of its vertex set divided by 2, then its connected. I was initially ...
26 views

### Cartesian power of what simple graph will have very poor connectivity?

Start from a simple connected graph G with finite vertices, we could take its cartesian power of order N. Now, what feature shall G have to reduce the connectivity of $G^{\Box N}$ (cheeger const or ...
61 views

### Bridgeless cubic graph has a 1-factor not containing two arbitrarily prescribed lines

According to Petersen's theorem, every bridgeless cubic graph has a perfect matching. While studying the proof of Petersen's theorem I came accross the following theorem "every bridgeless cubic graph ...
68 views

### Place bounds on the chromatic number of G given its maximum number of components

Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from ...
288 views

### Algorithm to compute maximum independent set of graph with maximum block size k with comlexity $O(f(k)\cdot p(|V(G)|)$

Definitions Definition block: Let $G$ be a undirected Graph. A maximal 2-connected subgraph (subgraph without biconnected component) of $G$ is called a block. Definition maximum independent set: An ...
28 views

### Show that a bridge is incident on a maximum degree vertex

Let $G$ a graph such that $|V(G)| = p, \Delta(G) = p-1$ and $\delta_G(x) = \Delta(G)$ for some $x \in V(G)$. Show that if $e$ is a bridge of $G$ then $x$ is an endpoint of $e$. I have so many doubts ...
536 views

### prove that if $G$ is a graph with $n$ vertices and $\delta(G) \geq (n - 1) / 2$ then $G$ is $\frac{n-1}{2}$-edge-connected

So I know $G$ is connected since $\delta(G)\geq(n-1)/2$, we can simply prove it by contradiction. My approach to this question is use contradiction. Suppose that $G$ is not $\frac{n - 1}{2}$- edge - ...
82 views

### Prove that if a graph is k-connected, then it is also k-edge-connected

Here is my thought, first if it is k-connected, then every vertex has degree at least k. So removing a set of size k-1 edges will not result any isolated vertices. I don't know how to continue.
378 views

### A 2-connected graph contains a path passing through all the odd degree vertices

I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no ...
### Show that if $G$ is $k$-connected and $H$ is $t$-connected then $G+H$ is $(k+t)$-connected
The exercise is given as the title says, I've just watched in this question the case of $K_1$ so I do wonder, do I have to make a similar proof? Or there's a different way to make it? Proof(Attempt): ...