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

125 questions
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.
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 ...
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 ...
0answers
10 views

1answer
41 views

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