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

350 questions
Filter by
Sorted by
Tagged with
26 views

### 2-connected graphs that contain no even cycle have a very simple structure

I recently received as an exercise the statement « 2-connected graphs that contain no even cycle as a subgraph have a very simple structure. » I then had to describe that structure and prove it. I did ...
45 views

### Prove that we can turn a hypercube into a tree by deleting the correct number of edges

An $n$-dimensional hypercube has $n2^{n-1}$ edges, and a tree has $n-1$ edges where $n= |V|$, so I know we need to delete the difference of these 2 quantities if we wanted to obtain a tree. However, I ...
3k views

### Euler's formula doesn't work for null graph?

Given the null graph with no edges or vertices, we have a connected planar graph as no edges cross when this graph is drawn in the plane, and the fact that any two distinct vertices have a path ...
64 views

### The connectivity of a simple graph

Let $G = \langle V, E \rangle$ be a simple graph such that $|V| = 7$ and $|E| = 16$. Denote the number of G's components by $\alpha$. Is it necessary that $\alpha = 1$? I think that the statement is ...
103 views

### Construct some special non-Hamiltonian graphs.

The following theorem is well known. Theorem 1. If $G$ is a graph containing a set $S \subset V(G)$ such that $G-S$ has more than $|S|$ components, then $G$ is not Hamiltonian. We know the converse of ...
89 views

### An extremal problem concerning sizes and connectivity.

Inspired by this question, we can ask a more general question. Question 1. Let $G$ be a connected graph with $n$ vertices and $m$ edges. Let $C$ be a cycle of $G$ such that after deleting all edges ...
1 vote
74 views

### Find a minimum 2-connected 5-regular non-Hamiltonian graph

Inspired by the post. According to this paper, there are $k$-connected $k$-regular non-Hamiltonian graphs for $k=4$ and $k \ge 8$ but the other cases are not shown there. Now I need to construct a 2-...
24 views

### Is there a specific noun for graphs with exactly connectivity $k$?

The (vertex-)connectivity $\kappa(G)$ of a graph $G$ is the minimum number of vertices whose removal from $G$ leaves a disconnected or a trivial graph. A graph $G$ with connectivity $\kappa ≥ k ≥ 1$ ...
78 views

### If a graph is 2-vertex-connected, then it can be produced by $K_3$, using only edge division and addition

I want to prove that if a graph is 2-vertex-connected, then it can be produced by $K_3$ (the simple triangle), using only edge division ("splitting" an edge, $(u,v)$, by creating a new ...
47 views

### minimum degree of 2-connected graph

If we have a 2-connected graph G, then can we say that δ(G) > k(G)? I need that in order to use Halin's theorem. Can we have then a more general relation between k-connected graphs and their ...
39 views

### Let $G$ be a biconnected graph, $\{x,y\} \subseteq V(G)$ be a separator. Show that if $e=\{x,y\} \in E(G)$, then $G\backslash e$ is biconnected.

Let $G$ be a biconnected graph, let $w,z \in V(G)$ and $e=\{x,y\} \in E(G)$. Here's my try: It will be shown that, there are two internally distinct paths joining vertices $w,z$ (so $G\backslash e$ is ...
1 vote
38 views

### Biconnectivity of two subgraphs

Let's say we have two graphs $G$ and $H$ with exactly two common vertices $u$ and $v$ and one common edge $uv$ and we know that graph $G \cup H$ is biconnected. Is it true that $G$ and $H$ are ...
1 vote
54 views

### The conjuction of two graphs is connected iff one of them has an odd cycle

The following is a dublicate of the question presented here: Let $G$ and $H$ be simple graphs. We build the graph $G\times H$ such that every vertex $(u,v) \in V(G\times H)$ is an ordered pair of one ...
1 vote
98 views

### The connectedness of dual graph

Prove: if a planar graph $G$ is $k$-vertex-connected, then so do its dual $G^{\ast}$ for $k=2,3$. And find a counterexample for $k=4$. I only have a vague idea for $k=2$: if $G$ has a cut vertex, then ...
1 vote
50 views

### Prove Lemma 3.3: “Let G be a 2-connected graph. If e and f are parallel edges in G, then G\e is 2-connected.”

I have to prove the Lemma stated in the Title. What I have so far is the following: Since two edges that form a cycle of length 2 are parallel edges, I need to prove that G\e contains such a cycle. ...
1 vote
18 views

### Havel-Hakimi algorithm for multi-edge graph

This question is inspired by this challenge and this paper. In the paper it is claimed that it is possible to use the algorithm so that the resulting graph will always be connected if a connected ...
113 views

### Vertex version of Menger's Theorem by its edge version

Menger's theorem is a well-known result from Graph Theory that characterizes the connectivity of a graph. In the literature, we may find four possible statements, depending on whether the graph is ...
30 views

### Identifying neighboring edges of subsquares using Python

I have 12 edges, marked from 0 to 11. There are 4 squares marked in red from 0 to 3. How do I identify the neighboring edges of each square? For example, square 0 has edges [0,2,3,5], square 1 has ...
520 views

### Can a DAG have strongly connected components?

It seems to me, a DAG (the directed graph has no cyclic.) is not possible to have strongly connected components (SCC), but it can have weakly connected components (WCC). The definition of SCC and WCC: ...
1 vote
91 views

### If $S$ is a minimum $k$- restricted-edge-cut of $G$, then must $G-S$ have exactly two connected components?

An edge cut is a set of edges that, if removed from a connected graph, will disconnect the graph. For a connected graph $G=(V ,E)$, an edge set $S ⊂ E$ is a $k$-restricted-edge-cut, if $G−S$ is ...
54 views

### Prove that a graph with a cycle for every $n+1$ vertices is $n$-connected.

Let $G$ a graph with at least $n+1$ vertices. Suppose that for every $n+1$ vertices $(v_1,\ldots,v_{n+1})$ exists a cycle which traverses the vertices in the given order. Prove that $G$ is $n$-...
61 views

### What is the relationship between a local minimal cut and a global minimal cut?

An edge cut is a set of edges that, if removed from a connected graph, will disconnect the graph. A minimal edge cut is an edge cut such that if any edge is put back in the graph, the graph will be ...
29 views

### How to calculate or approximate the edge connectivity of a subgraph?

I want to know the relation between the connectivity of part of graph and the overall graph. Assume that I have a graph $G = (V, E)$, then I want to calculate or approximate the edge connectivity of ...
61 views

### Minimal number of nodes to connect a given set of nodes [duplicate]

Let $G=(V,E)$ be an undirected graph and let $U \subset V$. Is there an algorithm that could find a minimal set of nodes that need to be added to $U$ so that the subgraph generated by the added nodes ...
88 views

### 2-connected graph is Hamiltonian

I tried to prove this: If $G$ is a $2$-connected graph with independence number $2$, then $G$ is Hamiltonian. I was thinking to construct de hamiltonian cycle. We know that $G$ has independence number ...
1 vote
67 views

### How to prove that the graph constructed below is still $k$-connected

I have often seen the following construction for $k$-connected graphs in some papers (especially involving planar graphs). Let $G$ be a graph. Let $x$ be a vertex of $G$. The Neighbourhood of the ...
30 views

### Infinite Maze of Squares with Random Thin Walls: Bounded?

A finite maze is generated as follows: A N×N grid of squares, where N is odd, and each border between two squares, or between a square and the outside of the N×N grid, has a p% chance of being a wall. ...
92 views

### Minimum number of edges to be added so that one can reach all vertices from root?

Here 1 is the root by adding edge from 1 to 3 and 2 to 4 one can reach all vertices from 1. What's the algorithm for achieving this?
99 views

### Graph connected, exists a path containing at least one vertex of each of the four colors.

I am trying to prove that if G is a 2-connected graph of order 4 or more such that each vertex of G is colored with one of the four colors red, blue, green, and yellow and each color is assigned to at ...
1 vote
132 views

### Let G be a k-edge-connected graph with n ≥ 3. For any e ∈ E(G), show that G/e is k-edge- connected.

Could someone help me with this question. My thought is that proof by contradiction. But I don't know which direction should I start with...
1 vote
47 views

### Existence of Euler $uv$-path $\iff$ all vertices except possibly u,v are even

A statement in my course says that : “A connected graph $G$ contains an Euler $uv$-path if and only if all vertices except possibly $u,v$ are even.” I agree with the $\implies$ direction, but in the ...
164 views

### Connected Regular Graphs on 12 vertices.

I'm trying to get a list of regular graphs on 12 vertices in g6 format. I've spent a few days trying to unscramble the data at the Regular Graphs Page, but I can't unscramble the shortcode format. ...
41 views

### Connectivity bounds for random regular fixed degree graphs with edge deletions

Let $G = (V, E)$ be a very large random graph of fixed degree (in my case, 3) , i.e., a regular graph. Let $\epsilon_i$ be independent Bernoulli random variables, s.t. $\epsilon_i \sim f(n)$ where $n$ ...
1 vote
38 views

### Connectivity of random regular multigraphs

For even integers $n$ and integers $3\le r < n$, is it true that a random $r$-regular multigraph on $n$ labelled vertices, obtained as the union of $r$ independent uniformly random perfect ...
33 views

### Connectivity of random collections of cubes

Imagine a cube $100\times100\times100$, a million little cubes. We randomly pick half of them to be red, half to be blue. Define "connected" to mean, two red cubes sharing a face. (You could ...
1 vote
192 views

### Given an arbitrary vertex connectivity $\kappa$, is there a graph that satisfies $\kappa(G) > \alpha'(G)$？

The problem described in the title comes from my previous question: Find the relationship between vertex connectivity and mathcing number. I think it is necessary to take it as a new problem. For ...
1 vote
101 views

### Find the relationship between vertex connectivity and mathcing number.

Some standard concepts: The vertex connectivity of a graph $G$, written as $κ(G)$, is the smallest number of vertices whose deletion from $G$ disconnects $G$. The matching number $\alpha'(G)$ of ...
123 views

### Induced Subgraph with the Largest Number of Edges

Is there an efficient way to find the induced subgraph with the largest number of edges among all the induced subgraphs of the same size? For example, I have a 200-node graph H and I would like to ...
114 views

### Does a triangulation $T$ such that $\kappa(T)=3$, $\kappa'(T)=4$ and $\delta(T)=5$ exist?

Some terminology and notation: A simple plane graph in which all faces are triangular faces is called a triangulation. The vertex connectivity of a graph $G$, written as $\kappa(G)$, is the smallest ...
### Is it possible to disconnect a bipartite vertex and edge transitive multigraph by removing $k$ edges without isolating a vertex?
Let $\Gamma$ be a finite connected bipartite $k$-regular multigraph (for $k\ge 3$) which is both vertex and edge transitive. Here by regularity I mean every vertex has $k$ edges incident to it. By ...