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
0
votes
0
answers
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
0
votes
1
answer
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) ...
0
votes
1
answer
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 𝐺...
- 9
2
votes
1
answer
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
2
votes
0
answers
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....
0
votes
0
answers
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
0
votes
1
answer
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
0
votes
0
answers
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
1
answer
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
1
answer
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
2
votes
1
answer
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
0
votes
1
answer
38
views
Let $G$ be an $r$-regular graph with $|V(G)| = 2r + 1$. Prove that $\lambda(G) = r$ (edge-connectivity).
Let $G$ be an $r$-regular graph with $|V(G)| = 2r + 1$. Prove that $\lambda(G) = r$ (edge-connectivity). On the exam, I solved the problem in one direction by considering the fact that in any graph $\...
user1316790
0
votes
0
answers
14
views
What can't be added for "maximally connected graph" to keep some property said in definition?
In wikipedia it says
A graph is said to be maximally connected if its connectivity equals its minimum degree. A graph is said to be maximally edge-connected if its edge-connectivity equals its ...
- 416
0
votes
0
answers
18
views
Prove that minimal disconnecting set is a cut. (Definitions included in the body).
Definitions
1.) Given a connected graph $G$, the minimal disconnecting set is the set of minimum number of edges that needs to be removed so that $G$ has more than one component.
2.) A cut is a set of ...
- 628
0
votes
0
answers
35
views
Prove that edge connectivity of a complete graph with $n$ vertices is $n-1$
Question
How to quickly see that the edge connectivity (minimum number edges to be removed to make a connected graph have more than one component) of a complete graph having $n$ vertices is $n-1$?
...
- 628
0
votes
1
answer
41
views
A connected k-regular bipartite graph is 2-connected. With the examples show, that we really need all the assumptions.
Prove: A connected k-regular bipartite graph is 2-connected. With the examples show, that we really need all the assumptions.
I was able to prove this theorem (as here: A connected k-regular bipartite ...
user1316790
2
votes
1
answer
61
views
Prove that for every graph $G$, it holds that $|V(G)| \geq \kappa(G) \cdot (\text{diam}(G) - 1) + 2$. Find example for equality.
Prove that for every graph $G$, it holds that $|V(G)| \geq \kappa(G) \cdot (\text{diam}(G) - 1) + 2$. For $k \in \{1,2\}$ and $d \geq 2$, find an example of a $k$-connected graph with diameter $d$ for ...
user1316790
4
votes
1
answer
84
views
$G$ 3-connected graph, $xy \in E(G)$. $G'$ graph obtained from $G$ by removing the edge $xy$ and merging the vertices $x$ and $y$ into one vertex.
Let $G$ be a $3$-connected graph and $xy \in E(G)$. Let $G'$ be the graph obtained from $G$ by removing the edge $xy$ and merging the vertices $x$ and $y$ into one vertex. Prove: The graph $G'$ is $3$-...
user1315539
2
votes
1
answer
30
views
Proving lower bound for the length of a cycle in a 2-connected graph.
I'm trying to prove that every 2-connected graph $G$ has a cycle $C$ such that $\vert C\vert\ge\text{min}(\vert G\vert,2\kappa(G)$ where $\kappa(G)$ is the connectivity of the graph (may be larger ...
- 402
1
vote
1
answer
77
views
Are all 2-connected graphs planar?
I know that all trees are planar, and so now I'm wondering whether 2-connected graphs are necessarily planar. I would imagine that this is true given that all 2-connected graphs have an ear ...
- 927
0
votes
0
answers
26
views
Simple graph connectivity when minimum degree is $\geq \frac{n-1} {2}$
Essentially the title, but we had to prove that the simple graph is connected. I know the standard way of doing this by assuming two components and then contradiction. But i wanted to know about ...
- 95
0
votes
1
answer
33
views
Special form of 3 vertex-connectedness for Graphs with every edge contained in a perfect matching
I am currently struggling with the following problem:
Given a simple, connected Graph $G = (V,E)$ such that every edge is contained in a perfect matching of $G$.
Show that for each edge $e \in E$ (of ...
- 673
0
votes
0
answers
25
views
Triangle is $2$-connected or $3$? [duplicate]
A connected graph is $k$-connected if either after removing any $k−1$
vertices the remaining graph is connected.
If I follow the definition,triangle is $3$-connected $(k=3)$ since removing any two ...
user1290851
0
votes
2
answers
80
views
Proof: If connected graph G has only one cut-vertex, then every longest path contains the cut vertex.
This is one of exercises from my uni's Discrete math problems. (Non-mandatory) And the job is to either found a counterexample or prove it.
I considered approaching this problem using proof by ...
- 397
1
vote
1
answer
59
views
The relationship between cyclic connectivity and vertex-disjoint cycles.
My question stems from the article "M. D. Plummer, On the cyclic connectivity of planar graphs" (1972). Before asking my question, the following necessary definitions and explanations are ...
- 2,504
0
votes
0
answers
96
views
Prove or disprove "one simple connected graph $G_n$ has no vertex of degree more than two if and only if it is $C_n$ or $C_n$ with one edge removed"
Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I did only the even-numbered exercises which the author offers the detailed description instead of the odd ...
- 416
2
votes
1
answer
53
views
If the bridges of a $3$-regular graph $G$ lie on a single path then $G$ has a $1$-Factor (perfect matching)
If the bridges of a $3$-regular graph $G$ lie on a single path then
$G$ has a $1$-Factor (perfect matching)
I've proved that a $3$-regular graph with at most two bridges has a perfect matching ($1$-...
- 853
2
votes
1
answer
43
views
Understanding why every 3-connected graph that is not $K_4$ has an edge such that suppressing an end also gives a 3-connected graph
I am reading Diestel graph theory rn.
$\newcommand{\dotdiv}{\mathbin{\rlap{\;{}^{\boldsymbol{\cdot}}}-}}$The definition of $G\dotdiv e$ is as follows: it is the multigraph obtained from $G-e$ by ...
- 107
0
votes
1
answer
28
views
Weighted colouring nodes in a graph, based on other already-coloured nodes
Say you have a directed acyclic graph. Any node can have a colour or
colours. The colours a node has are weighted -- e.g. a node which is
only red has red with weight 1; a node with highly weighted ...
- 103
1
vote
1
answer
105
views
Need help with a weird Graph Theory Proof about "quasi-factorizable" graph
I need help formulating proof for a graph-theory problem:
A graph $G = (V, E)$ is called quasi-factorizable if $G − u$ has a perfect matching for every vertex $u ∈ V$.
Show that $G$ is quasi-...
- 13
2
votes
1
answer
102
views
G a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$.
Let $k \geq 1$ be an integer, and let G be a k-connected bipartite graph with bipartition $(A, B)$ such that $|A|$, $|B| \geq 2k$. Show that $G$ contains a matching of size $2k$.
I have managed to ...
0
votes
1
answer
46
views
Connectivity of bipartite graph
We consider $G$ to be a bipartite graph that is $(d \geq 1)$-regular and has at most $4d-1$ vertices. We wish to show that $G$ must be connected.
My thinking was to prove by contradiction. So $G$ has ...
- 401
0
votes
1
answer
161
views
If a simple graph $G$ is not connected, then $\overline{G}$ is connected
Let $G=(V,E)$ be a simple graph with $E \subseteq P_2(V)$ and define $\overline{G}=(V,\overline{E})$ as the complement graph.
Show that if $G$ is not connected, then $\overline{G}$ is connected.
I ...
- 903
2
votes
1
answer
647
views
Let G be a connected graph in which every vertex has degree three. Show that if G has no cut-edge then every two edges of G lie on a common cycle.
"Let $G$ be a connected graph in which every vertex has degree three. Show that if $G$ has no cut-edge then every two edges of $G$ lie on a common cycle."
I have an idea for this proof but I'...
- 115
2
votes
1
answer
246
views
Graph theory proof - if $G$ is $2$-connected then for each $u$ there exists $v$ and a cycle $C$ that includes $u, v$ and all of $v$'s neighbors
Need to prove that if $G$ is $2$-connected then then for each $u$ there exists a $v$ and a cycle $C$ that includes $u$, $v$ and all of $v$'s neighbors.
I have reached an insight that all vertices must ...
- 43
1
vote
0
answers
59
views
How to extract a connected tree of nodes from undirected graph with certain attributes?
I am working on a problem where I need to extract a connected tree of nodes based on certain attributes while optimizing for the minimum number of nodes. Some attributes of the nodes are known in ...
- 41
2
votes
1
answer
55
views
Name of the edge whose removal causes the graph to be weakly connected
Given a strongly connected digraph G, there exists an edge that, when removed, makes the graph weakly connected. What is this edge called?
- 95
1
vote
1
answer
42
views
Subdivision of G has same connectivity as G
(I am referring to vertex connectivity). It seems intuitive to me that a subdivision of a graph cannot have smaller connectivity, however I am struggling to find a proof of this. Specifically, $K_k$ ...
- 13
0
votes
1
answer
71
views
Determine if each of the following graphs is connected and/or super-connected. Briefly justify your responses. [closed]
I am struggling to answer this question, and I was hoping for some assistance and/or help, it would be greatly appreciated.
This link is a screenshot of the question because it does include diagrams:
...
- 31
2
votes
1
answer
88
views
Which graphs remain connected when any connected subgraph is removed?
Which graphs remain connected when any connected subgraph is removed?
For example, complete graphs; $K_n$ or cyclic graphs; $C_n$ , fulfill this. Can someone give an example of another that is neither ...
- 161
1
vote
2
answers
109
views
graphs that when removing any path are still connected
My question is this:
Which graphs remain connected when any path is removed?
For example, complete graphs, $K_n$, fulfill this. Another example are the cyclic graphs, $C_n$. Can someone give an ...
- 161
0
votes
0
answers
104
views
How to show κ′(G) = δ(G) for δ(G) ≥ ⌊n/2⌋
I'm really struggling with the following proof.
Prove that if G is an n-vertex graph and δ(G) ≥ ⌊n/2⌋, then κ′(G) = δ(G).
My first thought was to construct a proof by contradiction, however, it ...
- 804
3
votes
0
answers
93
views
Minimum cost k-edge connected subgraph
I read somewhere that the problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with ...
- 31
2
votes
0
answers
137
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
78
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 ...
- 3,209
37
votes
1
answer
4k
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 ...
- 3,209
2
votes
0
answers
70
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 ...
- 1,062
4
votes
1
answer
115
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 ...
- 2,504
2
votes
0
answers
108
views
An extremal problem concerning sizes and connectivity. [closed]
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 ...
- 2,504
1
vote
1
answer
99
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-...
- 2,504