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
2
votes
0
answers
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 ...
- 31
0
votes
1
answer
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 ...
- 1,673
34
votes
1
answer
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 ...
- 1,673
2
votes
0
answers
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 ...
- 865
4
votes
1
answer
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 ...
- 1,978
3
votes
0
answers
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,978
1
vote
1
answer
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-...
- 1,978
0
votes
0
answers
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$ ...
- 1,978
2
votes
1
answer
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 ...
0
votes
1
answer
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 ...
0
votes
0
answers
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
1
answer
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 ...
- 11
1
vote
0
answers
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
3
answers
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 ...
- 355
1
vote
0
answers
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.
...
- 33
1
vote
1
answer
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 ...
- 744
0
votes
0
answers
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 ...
- 21
0
votes
0
answers
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 ...
- 139
3
votes
1
answer
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:
...
- 133
1
vote
1
answer
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 ...
- 1,978
3
votes
2
answers
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$-...
- 214
0
votes
1
answer
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 ...
- 1,978
0
votes
0
answers
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 ...
- 13
0
votes
1
answer
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 ...
- 379
4
votes
1
answer
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 ...
- 214
1
vote
1
answer
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 ...
- 1,978
2
votes
0
answers
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. ...
- 201
0
votes
1
answer
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?
- 9
2
votes
1
answer
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 ...
- 71
1
vote
1
answer
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...
- 23
1
vote
0
answers
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 ...
- 1,703
3
votes
2
answers
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.
...
- 20.6k
0
votes
0
answers
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$ ...
- 95
1
vote
1
answer
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 ...
0
votes
0
answers
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 ...
- 101
1
vote
1
answer
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,978
1
vote
1
answer
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 ...
- 1,978
2
votes
1
answer
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 ...
- 21
2
votes
1
answer
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 ...
- 1,978
3
votes
1
answer
88
views
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 ...
2
votes
1
answer
118
views
An undirected graph is partitioned. For every partition $V_1 \cup V_2 = V$, $v_1 \in V_1$ is connected to some $v_2 \in V_2$. Show it is connected.
We have an undirected graph $G = (V, E)$ partitioned into two non-empty subsets $V_1 \cup V_2 = V$. For this graph it holds that $(V_1 \cup V_2 = V) \implies (\exists v_1, v_2 : v_1 \in V_1 \land v_2 \...
- 890
0
votes
1
answer
41
views
Adding edges in two graphs with same connectivity, the connectivity is still maintained?
Let $G$ be a graph. Denote $G[A] = (V(G),A)$.
We say that two vertices $x$ and $y$ are connected in $G$, if there exists a path from $x$ to $y$ in $G$.
Let $I \subseteq E(G)$ and $I' \subseteq E(G)$ (...
- 113
1
vote
0
answers
124
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 ...
- 2,390
4
votes
2
answers
479
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 ...
- 155
0
votes
1
answer
45
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 ...
- 379
2
votes
1
answer
44
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/...
- 1,123
1
vote
2
answers
43
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$ (...
- 113
3
votes
1
answer
47
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 ...
- 426
0
votes
0
answers
49
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 ...
- 5,700
0
votes
0
answers
38
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 ...
- 77