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

312 questions
Filter by
Sorted by
Tagged with
41 views

### The contraction two graphs maintain the connectivity?

Let $G$ be a graph. For $X \subseteq E(G)$, define $G[X] = (V(G), X)$. I know that $u$ and $v$ are connected in $H[A]$ if and only if $u$ and $v$ are connected in $H[B]$ and let $Z \subseteq E(H)$ ...
29 views

### Showing edge-connectivity greater than vertex-connectivity

The following is quoted from Diestel's Graph Theory: Proposition 1.4.2. If $G$ is non-trivial then $\kappa(G) \leqslant \lambda(G) \leqslant \delta(G)$. Proof. The second inequality follows from the ...
97 views

### What is the probability that two nodes are connected in a random graph?

I have just started with the theory of random graphs. I have come across the following expression of the probability that two nodes $i$ and $j$ are connected where $k_i$ and $k_j$ are the respective ...
29 views

### Subset of the plane with no infinite set of disjoint $A-B$ arcs.

I want to find a subset $D$ of the plane such that has two infinite setss $A,B\subseteq D$ for which every finite set $X\subseteq D$ there is an $A-B$ arc in $D-X$ but $D$ contains no infinite set of ...
38 views

### A Result on Cut Vertices

This is one of the steps used to prove Menger's theorem in question 4 part (iii) of https://uwaterloo.ca/combinatorics-and-optimization/sites/ca.combinatorics-and-optimization/files/uploads/files/...
31 views

### How I can show that the swap of edges not change the original connectivity

Let $G$ be a graph. We say that $u$ and $v$ are connected in $G$, if exists a path of $u$ to $v$ in $G$. I wish show the following: Let $F$ be a forest and $T_1$ a tree with $T_1 \subseteq F$ (...
42 views

### Finite orientation/colouring of an infinite clique graph

Let $X$ be an infinite set and consider the undirected clique graph $Q(X)$. That is, $Q(X)$ has an edge between $x$ and $x'$ in $X$ for every distinct $x$ and $x'$. My question is this: In what ...
30 views

### The only cut vertex in a graph

Let a graph $G$ be arbitrarily traversable from a vertex $v$, i.e., any trail in $G$ initiatng from $v$ ultimately results in an Eulerian $v-v$ circuit. Let $v$ be a cut-vertex in $G$. Is it true that ...
33 views

### Brooks' Theorem Time complexity

I am looking to derive an algorithm that finds, for every connected graph $G$ that is neither complete nor an odd cycle, a $\Delta(G)$-colouring in time $O(m+n)$. When we proved Brooks' theorem we ...
1 vote
70 views

### How can I show that for each $e = uv \in F_0$ we have $H[F^* \cup e]$ contains a cycle

First, I present some definitions. Let $G$ a graph. For each $Z \subseteq E(G)$, we denote the graph $G[Z]$ by the $(V(G), Z)$. Let ${\cal P}$ a partition of $V(G)$. Define the graph $G_{\cal P}$ ...
49 views

### Why is this simple proof of the fact $\kappa(G)\le \lambda(G)$ is wrong?

A standard result in graph theory(more specifically graph connectivity) is that $\kappa(G)\le \lambda(G)$, where $\kappa(G)$ is the size of vertex cut set of $G$ and $\lambda(G)$ is the size of the ...
1 vote
23 views

### Deduce the undirected edge version of Menger's theorem from the directed version

Menger's theorem says, in directed graph $G$, $k$ is the maximum number of arc-disjoint $st$-dipaths if and only if the size of the minimum $st$-cut is $k$. Use this version of Menger's theorem to ...
51 views

### Proving that disconnecting edges of a 3-edge-colorable graph are of the same color

I'm struggling to prove the following: Edges of a connected cubic graph G can be colored with 3 colors in such a way that no adjacent edges are of the same color. 2 edges were removed from the graph ...
84 views

### Finding a spanning tree with at least 100 leaves

I have the following graph theory problem: In a country there are pairs of towns connected by roads in such a way that you can get from any town to any by those roads. The president of the country ...
1 vote
59 views

### Finding optimal minimum rooted k-edge disjoint connected paths to build a feasible solution for the undirected version

Suppose we have an undirected weighted graph G with a root node, and the goal is to find minimum cost k-edge disjoint paths from the root node to each vertex. Now, suppose we create a directed version ...
31 views

### Relationship between the minimum cost rooted k-edge connected subgraph and the unrootd version in undirected graphs

In the undirected rooted k-edge connected subgraph problem, the goal is to find a minimum cost subgraph in which there are k edge-disjoint paths between the root and each vertex in the graph. The ...
40 views

### Can vertex connectivity of a plane graph be characterized by a special closed Jordan curve?

Let $P$ be a plane, and a simple closed curve $l$ on $P$ is separating if $P-l$ is not connected. My question is as follows. Question Let $G$ be a planar graph with connectivity $k$, and $\phi(G)$ be ...
7 views

### What are real life examples of the arc augmentation problem in tournaments, semicomplete digraphs or locally semicomplete digraphs?

Suppose we have a digraph $G=(V,A)$ that is not yet $k$-strong. Assuming parallel arcs are not allowed, as long as $|V|\geq k+1$ we can always add a number of arcs to $A$ to make $G$ $k$-strong. ...
28 views

### Does block graph with one vertex exists?

A definition on Wolfram and Wikipedia suggest to me that a block graph contains connected components. A graph with one vertex is connected. Since one-vertex graph has 1-component and not components, a ...
1 vote
39 views

86 views

### Examples based on a 2-connected graph.

According to Scott Smith 1984 Conjecture: In a $k$-connected graph, where $k \ge 2$, any two longest cycles have at least $k$ vertices in common. A 2-connected graph: every pair of longest cycles have ...
42 views

### Randomly matchable and bipartite class

I am curios to know at least one example of the following graphs: i) an infinite class of bipartite graphs that is randomly matchable; ii) an infinite class of non-bipartite graphs that is randomly ...
35 views

### Definition of "separate" in Diestels‘s Graph Theory

In Dietels Graph theory, he defined "separate" in chapter 1.4 as If $A, B \subseteq V$ and $X \subseteq V \cup E$ are such that every $A-B$ path in $G$ contains a vertex or an edge from $X$,...
1 vote
38 views

### Number of pairwise non isomorphic 2-connected graph with no $K_4^-$ minor

I had this question in my graph theory exam today, and I'm pretty sure I answered it wrong. We define $K_4^-$ as $K_4$ with one less edge. Find the number of pairwise non isomorphic graphs $G$, such ...
63 views

### A 2-connected graph example

$\textbf{Question:}$ In a $k$-connected graph $(k\ge2)$, any $k$ vertices lie on a common cycle. $\textbf{Proof:}$ Let $S$ be a given set of $k$ vertices and consider a cycle $C$ with the maximum ...
84 views

### Lower Bounds on edge connectivity for expander graphs

So I've been messing around with expander graphs, and since their advantage is to maintain a high 'connectivity' with a fixed degree, I wondered about their edge connectivity. Formally, fix $k \ge 2$ ...
1 vote
45 views

### How can a "bridge path" in an undirected graph be defined correctly/mathematically precisely?

How would you define an undirected graph containing a path solely of bridges like: Connected Subgraph<->*<->*<->*<->* (* node; <-> undirected edge) Alternatively: ...
29 views

### Checking reachability and specifying direction and color of edges of a bigraph

I need help in finding a solution to this problem and answering my questions: first: is there any particular name for this problem? second: how can we solve it? third: it is not always possible to ...
34 views

### Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

A uniformly random $r$-regular bipartite graph is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular bipartite graph ...
1 vote
165 views

### Question about maximal connected subgraph [closed]

A maximal connected subgraph of G is a connected subgraph of G that is maximal with respect to the property of connectedness. This is called a component of G. Visually, components of G are the pieces ...
61 views

### Proof that either $G$ or its complement $\bar{G}$ is connected by induction

I wrote the following inductive proof, but I don't know if it is valid and if there are any points that I'm missing. I got a bit lost trying to prove the inductive step. We prove this statement by ...
48 views

### Questions concerning connectivity of graphs

So, we have been working with graphs for a while now and the profesor has handed out some questions for us to think. There are 3 of them that caught my attention: May the graph with 4,3,3,3,3,1,1 ...
1 vote
31 views

### Ensure weak connectivity in all k-out k-regular graphs depending on the number of vertices

When generating a random k-out k-regular directed graph, each node chooses randomly a distinct set of k nodes and creates k out-edges to them. I've only found results to my first question where $P = 1$...
1 vote
45 views

### Does it matter where we start on an Euler graph?

For a graph to be an euler graph, all the vertices have to be of even degree...I was wondering "does which vertex to start matter?"...I played around and now I kind of think it doesn't ...
1 vote
44 views

### Partition of graph with $\lambda(G)$

Let $\lambda(G)=\min\{|X|:X \subset E(G) \wedge G-Y \text{ is not connected} \}$ (minimum number of edged to delete to disconnect conntected graph). Let $\lambda(G) = k > 0$. Show that there is ...
1 vote
38 views

### Proof verification on $2$-connected Graph

A Graph is $2$-connected iff each two vertices lie on the same cycle. Proof: left to right: Graph is $2$-connected if each $2$ vertices are connected with at least two disjoint paths(follows from ...
1 vote
87 views

### Definition of $\mathfrak a$-connected graphs?
A typical definition of a graph $G$ being $k$-connected ($k\in\mathbb N_0$) is this: $k<|G|$ (the order of $G$) and for $X$ being a subset of $V(G)$ such that $|X|<k$ holds $G\setminus X$ is ...
### Prove that $6$ regular graph is connected
My question is how to check whether $6$ regular graph with $16$ vertices is connected or not? I found that number of edges is $48$ and then because $48 < {15 \choose 2}$ we can't say anything about ...