Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
25 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 $\...
0 votes
0 answers
12 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 ...
4 votes
1 answer
78 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$-...
0 votes
0 answers
12 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 ...
0 votes
0 answers
25 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$? ...
0 votes
1 answer
28 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 ...
2 votes
1 answer
44 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 ...
2 votes
2 answers
109 views

Connectivity and minimum length

Prove that a simple graph $G$ is $2$-connected if and only if for every triple $(x, y, z)$ of distinct vertices, $G$ has an $x, z$-path through $y$ Thanks!
2 votes
1 answer
26 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 ...
0 votes
2 answers
67 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 ...
1 vote
1 answer
55 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 ...
2 votes
1 answer
1k views

Show that a $2$-connected graph with minimum degree greater than or equal to $3$, has a vertex $v$ such that $G-v$ is $2$-connected

Assume that $G$ is a $2$-connected graph with $δ(G)≥3$. Show that there is a vertex $v\in G$ such that $G−v$ is $2$-connected. This question is a duplicate, I'm aware. However as the author of that ...
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 ...
0 votes
1 answer
27 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 ...
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 ...
4 votes
2 answers
1k views

Proof that every 2-connected graph has at least one contractible edge.

I am trying to prove the following statement: An edge $e$ in a 2-connected graph $e$ is said to be contractible if $G/e$ is also 2-connected. Prove that every 2-connected graph of order at least 3 ...
1 vote
1 answer
53 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 ...
0 votes
0 answers
94 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 ...
2 votes
1 answer
50 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$-...
2 votes
1 answer
39 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 ...
4 votes
1 answer
187 views

Graph theory connected graph

I am studying graph thoery and come up with a thought that, if $G$ is acyclic graph with degree of every vertex is at least two then $G$ is connected! The graph is said to be disconnected if at least ...
1 vote
1 answer
101 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-...
0 votes
1 answer
27 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 ...
2 votes
1 answer
237 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 ...
2 votes
1 answer
80 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
45 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 ...
0 votes
1 answer
90 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 ...
2 votes
1 answer
586 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'...
1 vote
0 answers
58 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 ...
2 votes
1 answer
46 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?
1 vote
1 answer
39 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$ ...
1 vote
1 answer
256 views

every vertices except two in 2-connected graph can be linearly ordered in a specific way

Let $s$ and $t$ be vertices in $2$-connected graph $G$, prove that the vertices of $G$ can linearly ordered so that each vertex apart from $s$ and $t$ has a neighbor that is earlier in the order and a ...
0 votes
1 answer
64 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: ...
2 votes
1 answer
85 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 ...
1 vote
2 answers
100 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 ...
0 votes
0 answers
89 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 ...
3 votes
0 answers
85 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 ...
14 votes
2 answers
1k views

Prove that connected graph $G$ with $\delta (G)\geq 3$ contains a cycle $C$ such that $G-E(C)$ is still connected.

In a connected simple graph every vertex has a degree at least $3$. Prove that the graph contains a cycle such that the graph remains connected when the edges of this cycle are deleted. Source: https:...
3 votes
2 answers
991 views

Prove or disprove: If $P = x...y$ is a path in a $2$-connected graph $G$ then there is another $xy$-path $P'$, which is internally disjoint from $P$.

Prove or disprove: If $P = x...y$ is a path in a $2$-connected graph $G$ then $G$ contains another $xy$-path $P'$, which is internally disjoint from $P$. I'm not sure where to start with this. Any ...
2 votes
0 answers
108 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 ...
0 votes
1 answer
70 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 ...
36 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 ...
1 vote
3 answers
273 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 ...
4 votes
1 answer
113 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 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 ...
3 votes
0 answers
101 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
1 answer
94 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 votes
1 answer
127 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
86 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
2 answers
145 views

Prove that $\lambda (G) \leq r/2$ if $\kappa(G) = 1$ of r-regular connected graph $G$ and $r > 1$

This is a question I found on exercise book. But I dont think it is true. For example, this graph: It is an upsided triangle on the top, and a triangle at the bottom. In this case, $\lambda(G) > ...

1
2 3 4 5
8