Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
23 views

Prove that if a graph is k-connected, then it is also k-edge-connected

Here is my thought, first if it is k-connected, then every vertex has degree at least k. So removing a set of size k-1 edges will not result any isolated vertices. I don't know how to continue.
5
votes
1answer
359 views

A 2-connected graph contains a path passing through all the odd degree vertices

I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no ...
0
votes
0answers
18 views

Can we use the Laplacian to quickly check if removing edges from a graph breaks connectivity?

Given a connected graph $G$ and it's associated Laplacian $L$, I want to determine whether or not removing a pair of adjacent edges from the graph breaks connectivity in a computationally efficient ...
0
votes
0answers
10 views

About the properties of K-connectivity

The excersice is given as it follows: Let $G$ a $k-connected$ graph, $z_0 \in V(G) \text{ and } U = \{x_1, \dots , x_k \}$ a set with $k$ vertices such that $z_0$ is not in $U$. Show that for each $...
0
votes
2answers
21 views

Show that if $G$ is $k$-connected and $H$ is $t$-connected then $G+H$ is $(k+t)$-connected

The exercise is given as the title says, I've just watched in this question the case of $K_1$ so I do wonder, do I have to make a similar proof? Or there's a different way to make it? Proof(Attempt): ...
3
votes
1answer
42 views

Generalization of graph connectivity to edge cases (null graph, singleton graph)

I am looking for advice on what would be a reasonable or useful generalization of vertex- and edge-connectivity to the graphs with 0 and 1 vertices (null graph and singleton graph). Motivation: ...
1
vote
0answers
15 views

Question regarding removal of a perfect matching in bridgeless graphs

Suppose a connected bridgeless graph has a perfect matching. If we delete the edges forming the perfect matching, then will the graph be still connected? Will the graph be still bridgeless too? ...
1
vote
1answer
29 views

Show that if $\kappa(G) \leq 1$ then $\lambda(G) \leq \frac{\Delta(G)}{2}$

The exercise is givien as the title says, I can't see no point using that $\kappa(G) \leq \lambda(G) \leq \delta(G) \leq \Delta(G)$, but is the only inequality that I know related with the ...
0
votes
0answers
15 views

Show that the number of connected components are less or equal of the degree of vertex in a cut set.

The exercise is defined as it follows: Let $G$ connected and $W \subseteq V(G)$ a cut set with minimum cardinality. Show that if $x \in W$ then $\omega(G-W) \leq \delta(x)$. Where $\omega$ is the ...
0
votes
0answers
24 views

Characterization of Block Graphs

The exercise is given as it follows: If $G$ is connected with order at least $3$, then $G$ is a block iff for all edge $e \in E(G)$ and for each $\{u,v\} \in V(G)$ exists a walk $W$ such that it does ...
2
votes
2answers
61 views

Can we have an infinite tree in this graph?

Suppose that a graph has an infinite number of nodes set up as follows: let $V_n=\{a_{n,1},a_{n,2},\dots,a_{n,n-1}\}\cup\{b_n\}$ be a set of $n$ nodes. Let $V=\bigcup_{n=1}^\infty V_n$. I am ...
0
votes
1answer
66 views

How to Show a graph is 3-connected?

I am attempting to solve a proof given in class which states the following: A cubic tree is a tree whose vertices have degree either 1 or 3. Let T be a cubic tree and let G be a cubic graph obtained ...
2
votes
1answer
28 views

Strengthening of Menger's Theorem

Is there a proof or counterexample for the following strengthening of Menger's Theorem? Let $G$ be a $k$-connected graph. For some $x,y \in V(G)$, let $P_1, \ldots, P_{k-1}$ be $k-1$ internally ...
6
votes
6answers
2k views

Are these two graphs isomorphic? Why/Why not?

Are these two graphs isomorphic? According to Bruce Schneier: "A graph is a network of lines connecting different points. If two graphs are identical except for the names of the points, they are ...
0
votes
1answer
49 views

Show that if $G$ is connected then $L(G)$ is connected

Well, the exercise it's as the title says. I know that if $G$ is connected then for every pair of vertex $u,v$ in $G$ there's a walk between them. So when the Line Graph $L(G)$ is constructed those ...
0
votes
1answer
41 views

Explicit construction and proving or disproving expander graph for this family

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. In an expander graph most vertices are far apart ...
0
votes
0answers
14 views

Connectivity of planar embedding of graph

I would like to know some terminology regarding graph theory. In order to be specific, consider the following example. Consider an arbitrarily large 2D square lattice. This can obviously be embedded ...
0
votes
0answers
13 views

How to combine multiple small connectivity matrices into one?

I have two connectivity matrices m1 and m2 of nodes 1 and 2 respectively. m1 = [0 50 3 20 4 30] m2 = [1 20 6 10] In each matrix, the ...
1
vote
2answers
51 views

proving that graph G is a path

I want to prove that the connected graph $G$ with $\delta(G) = 1$ and each vertex has a degree of $1$ or $2$, is a path. Can you tell whether my proof is correct? Since $G$ is connected, there is a ...
1
vote
1answer
52 views

Show that if $|G| \geq 5$ and for each pair of vertices $u,v$ there is an $u−v$ Hamilton path then $\kappa(G) \geq 3$

Show that if $G$ is a graph with $|G| \geq 5$ such that for each pair of vertices $u,v$ there is an $u−v$ Hamilton path in $G$, then $\kappa(G) \geq 3$ I do not really have any idea how to start this ...
2
votes
0answers
136 views

Is every $f(k)$-vertex-connected graph the edge-disjoint union of two $k$-vertex-connected graphs?

Does there exist a function $f: \mathbf{N} \to \mathbf{N}$ such that every $f(k)$-vertex-connected graph $G$ can have its edges partitioned into two spanning subgraphs $G_1$, $G_2$ such that both of ...
3
votes
0answers
56 views

What are graph algorithms that benefit (in their time complexity) from using the Adjacency Matrix?

I'm trying to understand better the advantages of using the adjacency matrix (AM) graph representation, in the context of time complexity of graph algorithms (I know, AM is quadratic in space, but let'...
1
vote
1answer
47 views

A connected maximal graph $G$ with no cycles of length at least $k+1$ has $|V(G)| \leq k$ or has a cut-vertex when $k \geq 2$

Is the following true: A maximal graph $G$ with no cycles of length at least $k+1$ has $|V(G)| \leq k$ or has a cut-vertex when $k \geq 2$. Here maximal is taken to mean that no edge can be added ...
2
votes
1answer
31 views

What is the maximum connectivity of a planar graph?

The Icosahedral Graph is a simple 5-connected planar graph. Is there a 6-connected planar graph? In general, is there a theoretical maximum on the vertex connectivity of planar graphs? This is ...
0
votes
0answers
39 views

Vertex Connectivity of the Hypercube

I am revising my lecture notes about connectivity, but I am stuck regarding proof of $κ(Q_n) = n$. I am revising the proof by induction in D. West's book. For $d\leq1$, $Q_d$ is a clique with $k+1$ ...
3
votes
1answer
69 views

Confusion about the proof of Menger's Theorem in “Introduction to Graph Theory” by Douglas West

The proof of Menger's Theorem in the book "Introduction to Graph Theory" by Douglas West (2nd Edition; Page 167) has been divided into two cases. The second case assumes that "Every minimum $x,y$...
0
votes
0answers
61 views

Clarification of Edge-connectivity Menger's theorem

Edge-connectivity Menger's Theorem: A graph is k-edge-connected if and only if every pair of vertices has k pairwise edge-disjoint (p.e.d.) paths in between. I can see that the later "k" is actually ...
2
votes
1answer
173 views

Show any two edges in a 2-connected graph lie on a cycle

So I found some proofs on any two vertices would lie on a cycle, but stuck on dealing with edges. We can say any two edges are connected, but does that just imply they will be on a common cycle?
0
votes
1answer
30 views

How to verify that a problem is in co-NP or NP?

In my discrete maths class we dabble a little bit into complexity theory. The lecturer frequently makes remarks such as: " "Is a graph G of n vertices k-connected?" is a problem in co-NP, since if it'...
0
votes
1answer
30 views

The subgraph induced by the neighbourhood of a vertex

I have the connected graph as in picture 1 attached. Is it correct if I take the subgraph induced by the neighbourhood of the vertex "a" as in the picture 2 below? The neighbouring vertices of "a" ...
4
votes
0answers
40 views

Prove that a $d$-regular, $d$-edge-connected graph $G$ is tough when $d\geq3$.

Isn't something like shown below can happen where $d=3$ and $k=1$? If no, then how do we prove it. Here v is a vertex with degree $3$, and $C_1$, $C_2$, and $C_3$ are $3$ different components, then ...
3
votes
2answers
90 views

How many edges are needed to ensure k-connectivity?

In this post, assume that all the graphs are simple (no loops or multiple edges allowed) for simplicity. I will use the notion of vertex-connectivity: Definition. A graph $G$ is called $k$-connected,...
3
votes
1answer
62 views

Is there a word for “nodes that can reach every other node and itself again”?

This graph is a sub-graph of a larger one. But this sub-graph contains all nodes with a special characteristic. You can start at any point of the graph. You can reach every other node from there AND ...
2
votes
1answer
195 views

How demonstre that a graph is connected?

I was wondering if someone can help me understand how to prove this theorem . We consider the following binary operation $\otimes$ on graphs: if $G_i = (V_i,E_i) (i = 1,2)$ are two graphs, then $G_1 \...
3
votes
1answer
41 views

Question regarding connectivity number and maximum degree of a graph

I need to show for graph G,if $\Delta(G) \leq 3 $ then $\kappa(G) =\kappa^{'}(G)$. Where $\Delta(G) \ $ is the maximum degree of the graph , $ \kappa(G) $ is the vertex connectivity number and $\...
0
votes
1answer
137 views

Show that if G is a planar, simple and 3-connected graph, then the dual graph of G is simple and 3-connected

I've been thinking about this question for several days now and I haven't come up with a satisfactory answer yet. The part of proving that the dual graph is simple (under the assumption that the ...
2
votes
1answer
33 views

GI-Completeness of graph isomorphism with connected graphs

The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected ...
1
vote
0answers
19 views

Show that a connected simple graph for which every edge is in some perfect matching is a block [duplicate]

Show that a connected simple graph for which every edge is in some perfect matching is a block. It seems obvious to prove by contradiction. so Suppose such a graph $G$ has a cut-vertex $v$. The ...
0
votes
0answers
53 views

Find a simple graph with $\kappa = 1439$, $\kappa ' = 2018$, and $\delta = 5778$

Construct a simple graph $G$ with $\kappa (G) = 1439$, $\kappa '(G) = 2018$, and $\delta (G)= 5778$ and prove that it has these properties. Not sure how to approach this. I have a few ways of finding ...
1
vote
0answers
77 views

A measure of connectedness in graph theory

From Wikipedia: A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A tree is an undirected graph in which any two vertices are ...
3
votes
1answer
87 views

If every $H$-free $2$-connected graph is Hamiltonian then $H$ is $P_3$

I'm stuck with exercise 5 page 72 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory: Show that if being $H$-free implies Hamiltonicity in $2$-connected graphs (where $H$ is ...
0
votes
0answers
41 views

What connected graphs are with equal vertex-connectivity and minimum degree?

Let $G$ be a connected graph with equal vertex connectivity and minimum degree. What can we say about $G$? I am trying to find some literature about this question, but I was not able to. I will ...
2
votes
1answer
108 views

3-connected multigraph and parallel edge

In Diestel book, 5th edition, page 62, he says in the footnote "Recall also that 3-connected multigraphs cannot have multiple edges". Also, in the proof for Lemma 3.2.1, he uses "the fact" that "$G\,\...
0
votes
1answer
84 views

Complement of tree graph

I am trying to show that the graph complement of a tree graph $G$ is connected or has a unique isolated vertex and and the remaining nodes with its respective edges form a complete subgraph of $G$. ...
3
votes
1answer
216 views

strongly connected graph if and only if every edge belongs simple cycle

I am trying to show that the following property holds: Definition A digraph is called a strongly connected graph if given two vertices $x \neq y$, there exist the oriented paths $x \rightarrow y$ and ...
1
vote
0answers
127 views

Proving vertex form of Menger's Theorem et al. without using capacity of vertices.

I'm teaching an undergrad course in graph theory and have just finished the proof of Max Flow/Min Cut. So far I have used Diestel's definition (more or less) of flow network as a digraph $G$ with a ...
2
votes
2answers
93 views

Let $v$ be a vertex of a 2-connected graph $G$. Prove that $v$ has a neighbor $u$ such that $G − u − v$ is connected.

Let $v$ be a vertex of a 2-connected graph $G$. Prove that $v$ has a neighbor $u$ such that $G − u − v$ is connected. I'm not sure I understood that prove. Please anyone can explain me that ? Prove ...
3
votes
2answers
84 views

Let $G$ be a connected graph with $n>=3$ vertices.

Let $G$ be a connected graph with $n>=3$ vertices. Prove that if $G$ has an Euler Cycle than is has 3 vertices of the same degree. I thought using the Pigeonhole principle but I'm not sure how... ...
2
votes
0answers
83 views

What is the probability of a random graph being connected? [duplicate]

Suppose $G$ is a random simple graph, that has $n$ vertices, and edges, that are present independently with probability $p$. What is the probability of $G$ being connected? It is quite easy to ...
1
vote
1answer
54 views

Show that any two egdes of $e$ and $f$ lie on a common cycle of $G$.

$B$ is a nonseparable subgraph of $G$ that is not a proper subgraph of any other noseparable subgraph of $G$. Show that any two egdes of $e$ and $f$ lie on a common cycle of $G$. Let $C$ be a cycle ...