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.

1
vote
1answer
19 views

Graph Theory - Trees, Forest, Connected graph with 1 cycle.

I am struggling with visualizing this question. Suppose G is a simple graph with vertices V(G) = [5] and d(1) = 2, d(2) = 1, d(3) = 2, d(4) = 1. What is d(5) if G a forest with 2 components? A ...
2
votes
2answers
54 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
40 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
21 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 ...
5
votes
6answers
2k views

Are these two graphs isomorphic? Why/Why not? [closed]

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
22 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
38 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
10 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
48 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
37 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
107 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
55 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
38 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
23 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
32 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
63 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
38 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
105 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
29 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
24 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
37 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
80 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
45 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
191 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
37 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
110 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 ...
1
vote
0answers
55 views

Distributions of components in random geometric graphs

In the context of random geometric graphs where edges are assigned according to a distance criterion $d_{ij}\le \delta,$ with $d_{ij}$ denoting the Euclidean distance between the vertices $i$ and $j,$ ...
1
vote
1answer
48 views

If $G$ is a graph having $p$ vertices and min degree $\delta(G)\ge\frac{p-1}{2}$, then the edge connectivity is $\delta(G)$.

How to prove below statement. If $G$ is a graph having $p$ vertices and $\delta(G)\ge\frac{p-1}{2}$, then edge connectivity is $\delta(G)$
2
votes
1answer
32 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
46 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
61 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
85 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
35 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
84 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
72 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
160 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
102 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
71 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
67 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
76 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
48 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 ...
0
votes
0answers
45 views

3-Points on 3-vertex connected graph

I have to proof the following Let $v_1,v_2,v_3$ be any 3 vertices on a 3-vertex-connected graph $G=(V,E)$. Then they belong to a circle $C$ What I got so far. Any two vertices $ v_1,v_2 \in V$ ...
1
vote
1answer
70 views

Finding vertex-cut using Menger's theorem

Menger's theorem states that A Graph, $G$, is $k$-connected if and only if for every $x,y \in V(G)$, there exists $k$ pairwise internally disjoint paths. If I need to find size of vertex cut for ...
2
votes
1answer
33 views

How to find a Graph's $K_v$?

By $K_v$ I mean the minimun amount of vertices to be removed from a connected graph such that it loses its connectivity We define the Graph $G_n$ as a graph with $3^n$ vertices, where each vertex has ...
0
votes
0answers
16 views

Graph Theory :-Bi connected Graph

Prove:-If there are no articulation points in graph,then there exists two vertex disjoint paths between any two vertices. Background:- As per definition of biconnected graph,it says:- "An undirected ...
2
votes
0answers
104 views

planar graphs and number of faces

Show that no matter in what way we embed a planar graph, we always get the same number of faces. This is trivial for connected graphs, because Euler's formula applies and shows that $f = 2 - n + e$, ...
3
votes
1answer
127 views

Can edge-connectivity version of Menger's theorem be generalized for two subsets of vertices?

Specifically, let $G$ be an undirected graph and $S$ and $T$ be two (possibly intersected) subsets of vertices, is the size of the minimum edge cut for $S$ and $T$ equal to the maximum number of ...
3
votes
1answer
170 views

What is κ(G) and κ′(G) and δ(G) for graph G?

Am I correct to say that G is 4-connected? So κ(G) = 4 but then κ′(G)=2 but that cannot happen since κ(G)<=κ′(G)<=δ(G) I know δ(G)=4 so wouldn't κ′(G)=4 then? However, I don't see how that ...