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
1
vote
1answer
18 views

Proof check : In a connected simple undirected graph with degree of each vertex greater than $1$ there exists a cycle

Question : Let $G\left( V,E\right) $ be a connected simple undirected graph such that $deg\left( v\right) \geq 2\forall v\in V$ , then there exists a simple circuit in $G$ We start by removing ...
-3
votes
0answers
20 views

Show that the resulting graph $G$

To the disjoint union of the graph, $H = K_{2m+1}$ with $k$ copies of $K_{2m+1}$ add edges joining $H$ bijectively to each of the $K_{2m+1}$. Show that the resulting graph $G$ contains at most $km = \...
-1
votes
0answers
11 views
3
votes
1answer
75 views

Graph Theoretical Game: Repeatedly deleting a $C^k$ from a $K^n$

Having solved the following exercise, I wonder what happens if you change it slightly. Let $n \geq 4$. A bored mathematician plays the following game: She starts with a complete graph $K^n$. In ...
1
vote
0answers
18 views

Show that if G is a graph, then $κ(G) ≤ λ(G)$

Show that if G is a graph, then $κ(G) ≤ λ(G)$ where $κ(G)$ is vertex connectivity and $λ(G)$ is edge connectivity I have a solution that seems rather simple , could someone verify the correctness ...
0
votes
1answer
15 views

Show that if $G$ is $2-$connected, then for any two vertices $u$ and $v$ there exists a cycle $C$ such that $u, v \in V (C)$

Show that if a graph $G$ is $2-$connected, then for any two vertices $u$ and $v$ there exists a cycle $C$ such that $u, v \in V (C)$ I tried to use the fact that a graph $G$ with at least $3$ ...
1
vote
0answers
18 views

remove a vertex of a 2-connected graph without break 2-connected

suppose $G$ is 2-connected and $G$ is not a cycle, is it possible to prove that there exists a vertex $v$ such that $G-v$ is still 2-connected? $G-v$ means remove $v$ from vertex and all incident ...
0
votes
0answers
16 views

Number of connected subgraphs of complete labelled graph

What is an explicit formula or good approximation for the number of connected subgraphs with $m$ vertices and $k$ edges of the complete graph on $n$ labelled vertices? For $m=2$ and $k=1$, we obtain $...
0
votes
1answer
31 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) > ...
0
votes
1answer
22 views

How to prove this graph is connected?

If I have a simple graph G with p vertices $\geq 3$ and with a number of edges > $\frac{(p - 1) \cdot (p - 2)}{2}$, how can I prove it is connected?
0
votes
1answer
44 views

Questions related to Laplacian matrix of a Graph

I was reading a graph theory by Adrian Bondy and U S R Murty. In this textbook it is mentioned that for a simple finite graph $G,$ the Laplacian matrix $\mathbf{L}$ is a square symmetric matrix which ...
1
vote
1answer
72 views

k-connected graph, there exists a cycle that contains any 2 edges and any $k-2$ vertices

Question: Let $G$ be a $k$-vertex-connected graph with $k\geq2$. Let $S$ be a set of two edges and $W$ a set of $k-2$ vertices. Prove that there exists a cycle in $G$ containing elements of $S$ and $W$...
1
vote
1answer
33 views

A connected k-regular bipartite graph is k-connected.

I've seen the similar question "A connected k-regular bipartite graph is 2-connected" answered: A connected k-regular bipartite graph is 2-connected. Prove that every connected k-regular bipartite ...
1
vote
0answers
21 views

$G$ is $n$-edge-connected iff $L(G)$ is $n$-connected

Please, give me feedback if the following argument about a graph $G$ and its line graph $L(G)$ is acceptable. Let $G$ be a connected graph with minimum degree $\delta(G) \geq n > 1$. Then, $G$ is $...
0
votes
1answer
24 views

Maximum set of edges or vertices that doesn't disconnect graph

A graph is k-connected if every set of fewer than k vertices does not disconnect the graph, and a graph is k-edge-connected if every set of fewer than k edges does not disconnect the graph. The ...
0
votes
0answers
53 views

3 connected graphs

I am trying to understand the following Lemma: Let G be a 3 connected graph of order at lest five and x in V(G). Suppose degree of x in G is 3 and the set of vertices adjacent to x in G is {a,b,c}. If ...
0
votes
0answers
55 views

$k$-connectivity graph partitions

What is the right definition to generalise the following observations? 1. $1$-connectivity induces a partition of graph vertices into $1$-connected components 2. $2$-connectivity induces a partition ...
0
votes
0answers
51 views

With reference to an argument related to a spanning path in a connected $4$-regular graph

I have a 4-regular odd ordered connected graph, say $X$. It is a vertex transitive graph, so there exists a perfect matching for the graph $X-v$, for any vertex $ v \in X$. There I consider two ...
1
vote
1answer
73 views

Proving that articulation points lay on all paths between two vertices

Let $G = (V, E)$ be a simple connected undirected graph with $z \in V$. How can I prove the following claim. The vertex $z$ is an articulation point in $G$ if and only if there exists to distinct ...
1
vote
1answer
67 views

vertex connectivity proof

I was going through a graph theory book and found this Let $G$ be a simple undirected graph. $\kappa(G) <\frac{n}{2}$ . If $G$ is connected, then $G$ must contain a simple path of length at least ...
0
votes
0answers
26 views

Does a $k$-connected graph has $k$ totally disjoint $S-T$ paths for $|S|=|T|=k$?

I read about the question here: Prove that $G$ has $k$ pairwise disjoint $S$,$T,$ Paths? And I am interested in whether the result still holds for $S\cap T\neq \emptyset$. So the problem is: ...
2
votes
2answers
45 views

Is this an equivalent definition for connectivity in graphs?

Let $G=(V,E)$ be a simple graph. The usual definition of connectivity is: $G$ is connected iff for each pair of vertices $u,v\in V$, there exists a path between $u$ and $v$. I am fine with this ...
4
votes
1answer
180 views

A question regarding a $k$-connected graph

I would like to show several things, some for general $k$-connected graphs and some for several instances ($k=2,3,...$). First, I want to show that for every $k$-connected graph each subset $A\...
1
vote
0answers
67 views

Proving the generalization of Euler's formula for a graph $G$ with $k$ connected components: $V(G)-E(G)+F(G) = k+1$

Let $G$ be a planar graph. Let $V(G)$ denote its numbers of vertices, $E(G)$ its number of edges and $F(G)$ its number of faces. Show that if $G$ has $k$ connected components, then $$V(G)-E(G)+F(G) ...
0
votes
1answer
29 views

Hamilton decompositions of cycle plus triangles graphs

A cycle plus triangles graph is a 4-regular graph $G$ with a Hamiltonian circuit $C$ and such that the chords of $C$ induce a set of disjoint triangles (3-circuits). A 4-regular graph $G$ has a ...
0
votes
2answers
53 views

Does a k-connected graph contain a k-connected bipartite subgraph?

I have a problem where, when trying to solve it, I use some parts which would prove that a k-connected graph contains a k-connected bipartite subgraph. I am fairly sure that this can not be correct, ...
0
votes
1answer
37 views

Regular ternary ordered tree

I’m not too familiar with ordered tree. I’m solving excercise about tree but i’m not sure it is right or wrong How many regular ternary ordered tree with height 3 (ordered tree means children of each ...
0
votes
0answers
55 views

About a critical 2-connected graph

Let G be a critical 2-connected graph; this means that G is 2-connected but no graph G−e for e∈E(G) is 2-connected. Prove that at least one vertex of G has degree 2. My idea: proof by contradiction ...
0
votes
0answers
22 views

Classify isomorphism of graph

N and k are positive integers satisfying $ 1<=k < n$ An undirected graph $G_{n,k}= (V_{n,k} ,E_{n,k})$ is defined as follows. $V_{n,k}={1,2,3,...n}$ $E_{n,k}={\{\{u,v\}|u-v \equiv k \, (mod ...
1
vote
0answers
34 views

Expansion of 3-connected graphs gives 3-connected graphs

So I am working on this graph theory problem which says: An expansion of a graph $G$ is formed by subdividing two edges of $G$ (subdividing an edge $vw$ means replacing $vw$ with a path $vxw$ through ...
0
votes
1answer
37 views

k-edge-connectivity

For every positive integer $k$ construct an infinite family of graphs G with $\lambda(G)=k$ without using parallel edges in the construction. I can't construct infinite family of graphs that ...
0
votes
0answers
39 views

K-connected graphs

Let $k\geq3$. Prove that for every $n\geq k+1$, every $k$-connected $n$-vertex graph $G$, and every pair of disjoint vertex sets $S$ and $T$ in $G$ with $|T|=3$ and $|S|=k-3$, there is a cycle that ...
0
votes
1answer
49 views

Maximum matching in bipartite graph [closed]

Prove that for every bipartite graph G with bipartition {A, B}, the size of the maximum matching in G equals |A| − δ where $$ δ = max_{S⊆A} (|S| − |N_G(S)|) $$
1
vote
1answer
24 views

Question regarding circulant graphs

When I was studying about circulant graphs I came up with the following definition. A circulant graph with $N$ vertices and jumps $\{j_1, j_2, ..., j_m\}$ is an undirected graph in which each vertex $...
1
vote
0answers
25 views

Graphs “weak” in context of cutting subgraphs

This is an updated cross-post from MO: https://mathoverflow.net/questions/340215/graphs-weak-in-context-of-cutting-subgraphs where it didn't get much attention. Lately we've been looking into graphs (...
0
votes
0answers
58 views

Edge connectivity of bipartite subgraph.

Let G be a (2k-1)-edge connected multigraph. Show that G has a k-edge connected bipartite subgraph. I try to consider an induced bipartite subgraph H with maximum edge-connectivity t, and do an ...
1
vote
1answer
159 views

Maximum number of edges in minimally $k$-edge-connected multigraph

A graph or multigraph is $k$-edge-connected if it cannot be disconnected by deleting fewer than $k$ edges. It is minimally $k$-edge-connected if it loses this property when any edges are deleted. (...
0
votes
0answers
49 views

Polyamory Network problem

Two Related Problems: 1. Imagine polyamorous people form a complicated network. Define each person as a unique node. Define a relationship between two people as an edge. Each node can possibly ...
4
votes
1answer
143 views

Number of edges in a minimal $k$-edge connected subgraph

We know that any minimal connected subgraph of a connected graph with $n$ nodes has exactly $n-1$ edges. What are the known bounds (especially upper bounds) for the number of edges in a minimal $k$-...
2
votes
2answers
40 views

If Degree of a Vertex Greater Than/Equal to Size of Vertex Set / 2 then Connected

I encountered a question asking to prove that if the degree of every vertex is greater than or equal to the floor of the size of its vertex set divided by 2, then its connected. I was initially ...
0
votes
0answers
26 views

Cartesian power of what simple graph will have very poor connectivity?

Start from a simple connected graph G with finite vertices, we could take its cartesian power of order N. Now, what feature shall G have to reduce the connectivity of $G^{\Box N}$ (cheeger const or ...
2
votes
1answer
61 views

Bridgeless cubic graph has a 1-factor not containing two arbitrarily prescribed lines

According to Petersen's theorem, every bridgeless cubic graph has a perfect matching. While studying the proof of Petersen's theorem I came accross the following theorem "every bridgeless cubic graph ...
1
vote
1answer
68 views

Place bounds on the chromatic number of G given its maximum number of components

Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from ...
1
vote
1answer
288 views

Algorithm to compute maximum independent set of graph with maximum block size k with comlexity $O(f(k)\cdot p(|V(G)|)$

Definitions Definition block: Let $G$ be a undirected Graph. A maximal 2-connected subgraph (subgraph without biconnected component) of $G$ is called a block. Definition maximum independent set: An ...
0
votes
1answer
28 views

Show that a bridge is incident on a maximum degree vertex

Let $G$ a graph such that $|V(G)| = p, \Delta(G) = p-1$ and $\delta_G(x) = \Delta(G)$ for some $x \in V(G)$. Show that if $e$ is a bridge of $G$ then $x$ is an endpoint of $e$. I have so many doubts ...
1
vote
1answer
536 views

prove that if $G$ is a graph with $n$ vertices and $\delta(G) \geq (n - 1) / 2$ then $G$ is $\frac{n-1}{2}$-edge-connected

So I know $G$ is connected since $\delta(G)\geq(n-1)/2$, we can simply prove it by contradiction. My approach to this question is use contradiction. Suppose that $G$ is not $\frac{n - 1}{2}$- edge - ...
0
votes
0answers
82 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
378 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
2answers
41 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
62 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: ...