Mixing
Show any two edges in a 2-connected graph lie on a cycle
up vote
1
down vote
favorite
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?
discrete-mathematics graph-theory connectedness graph-connectivity
edited 2 days ago
Batominovski
31.5k23187
asked 2 days ago
Thomas
896
add a comment |
up vote
1
down vote
favorite
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?
discrete-mathematics graph-theory connectedness graph-connectivity
edited 2 days ago
Batominovski
31.5k23187
asked 2 days ago
Thomas
896
Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure.
– Batominovski
2 days ago
@Batominovski Here I'm referring to 2-vertex-connected.
– Thomas
2 days ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
discrete-mathematics graph-theory connectedness graph-connectivity
edited 2 days ago
Batominovski
31.5k23187
asked 2 days ago
Thomas
896
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?
discrete-mathematics graph-theory connectedness graph-connectivity
discrete-mathematics graph-theory connectedness graph-connectivity
edited 2 days ago
Batominovski
31.5k23187
asked 2 days ago
Thomas
896
edited 2 days ago
Batominovski
31.5k23187
asked 2 days ago
Thomas
896
edited 2 days ago
Batominovski
31.5k23187
edited 2 days ago
Batominovski
31.5k23187
edited 2 days ago
Batominovski
31.5k23187
31.5k23187
asked 2 days ago
Thomas
896
asked 2 days ago
Thomas
896
asked 2 days ago
Thomas
896
896
Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure.
– Batominovski
2 days ago
@Batominovski Here I'm referring to 2-vertex-connected.
– Thomas
2 days ago
add a comment |
Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure.
– Batominovski
2 days ago
@Batominovski Here I'm referring to 2-vertex-connected.
– Thomas
2 days ago
Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure.
– Batominovski
2 days ago
Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure.
– Batominovski
2 days ago
@Batominovski Here I'm referring to 2-vertex-connected.
– Thomas
2 days ago
@Batominovski Here I'm referring to 2-vertex-connected.
– Thomas
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Let $G = (V, E)$ graph, $|V| ge 3$. Suppose that there exists an edge $e = (u, v) in E$ such that $e$ does not lie on a cycle. Then every path from $u$ to $v$ must contain $e$ (1). If $u$ or $v$ are a leaf, then removing the vertex that connects the leaf from the rest of the graph makes the leaf disconnected (!). Otherwise, define the following partition of $G$ without $e$:
$$G_u = (V_u, E_u) quad quad G_v = (V_v, E_v)$$
where $V_u = {w in V |$ there is a path from $w$ to $u$ that does not contain $e}$, $E_u = {(w, t) in E | w, t in V_u}$ and $V_v$, $E_v$ are defined analogously (2). If we remove $u$ or $v$ from the graph, then we are also removing $e$. Note, however, that if we remove $e$, then there is no path to go from any $w in G_u$ to any $t in G_v$. In other words, the graph becomes disconnected (!).
Notes:
(1) Suppose that there exists a path from $u$ to $v$ that does not contain $e$. Then we can join this path to $e$ to form a cycle, but by doing so we are showing that $e$ lies on a cycle (!).
(2) It is easy to show that $G_u$ and $G_v$ are disjoint.
answered 2 days ago
Just_a_newbie
526
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Let $G = (V, E)$ graph, $|V| ge 3$. Suppose that there exists an edge $e = (u, v) in E$ such that $e$ does not lie on a cycle. Then every path from $u$ to $v$ must contain $e$ (1). If $u$ or $v$ are a leaf, then removing the vertex that connects the leaf from the rest of the graph makes the leaf disconnected (!). Otherwise, define the following partition of $G$ without $e$:
$$G_u = (V_u, E_u) quad quad G_v = (V_v, E_v)$$
where $V_u = {w in V |$ there is a path from $w$ to $u$ that does not contain $e}$, $E_u = {(w, t) in E | w, t in V_u}$ and $V_v$, $E_v$ are defined analogously (2). If we remove $u$ or $v$ from the graph, then we are also removing $e$. Note, however, that if we remove $e$, then there is no path to go from any $w in G_u$ to any $t in G_v$. In other words, the graph becomes disconnected (!).
Notes:
(1) Suppose that there exists a path from $u$ to $v$ that does not contain $e$. Then we can join this path to $e$ to form a cycle, but by doing so we are showing that $e$ lies on a cycle (!).
(2) It is easy to show that $G_u$ and $G_v$ are disjoint.
answered 2 days ago
Just_a_newbie
526
add a comment |
up vote
0
down vote
Let $G = (V, E)$ graph, $|V| ge 3$. Suppose that there exists an edge $e = (u, v) in E$ such that $e$ does not lie on a cycle. Then every path from $u$ to $v$ must contain $e$ (1). If $u$ or $v$ are a leaf, then removing the vertex that connects the leaf from the rest of the graph makes the leaf disconnected (!). Otherwise, define the following partition of $G$ without $e$:
$$G_u = (V_u, E_u) quad quad G_v = (V_v, E_v)$$
where $V_u = {w in V |$ there is a path from $w$ to $u$ that does not contain $e}$, $E_u = {(w, t) in E | w, t in V_u}$ and $V_v$, $E_v$ are defined analogously (2). If we remove $u$ or $v$ from the graph, then we are also removing $e$. Note, however, that if we remove $e$, then there is no path to go from any $w in G_u$ to any $t in G_v$. In other words, the graph becomes disconnected (!).
Notes:
(1) Suppose that there exists a path from $u$ to $v$ that does not contain $e$. Then we can join this path to $e$ to form a cycle, but by doing so we are showing that $e$ lies on a cycle (!).
(2) It is easy to show that $G_u$ and $G_v$ are disjoint.
answered 2 days ago
Just_a_newbie
526
add a comment |
up vote
0
down vote
up vote
0
down vote
Let $G = (V, E)$ graph, $|V| ge 3$. Suppose that there exists an edge $e = (u, v) in E$ such that $e$ does not lie on a cycle. Then every path from $u$ to $v$ must contain $e$ (1). If $u$ or $v$ are a leaf, then removing the vertex that connects the leaf from the rest of the graph makes the leaf disconnected (!). Otherwise, define the following partition of $G$ without $e$:
$$G_u = (V_u, E_u) quad quad G_v = (V_v, E_v)$$
where $V_u = {w in V |$ there is a path from $w$ to $u$ that does not contain $e}$, $E_u = {(w, t) in E | w, t in V_u}$ and $V_v$, $E_v$ are defined analogously (2). If we remove $u$ or $v$ from the graph, then we are also removing $e$. Note, however, that if we remove $e$, then there is no path to go from any $w in G_u$ to any $t in G_v$. In other words, the graph becomes disconnected (!).
Notes:
(1) Suppose that there exists a path from $u$ to $v$ that does not contain $e$. Then we can join this path to $e$ to form a cycle, but by doing so we are showing that $e$ lies on a cycle (!).
(2) It is easy to show that $G_u$ and $G_v$ are disjoint.
answered 2 days ago
Just_a_newbie
526
Let $G = (V, E)$ graph, $|V| ge 3$. Suppose that there exists an edge $e = (u, v) in E$ such that $e$ does not lie on a cycle. Then every path from $u$ to $v$ must contain $e$ (1). If $u$ or $v$ are a leaf, then removing the vertex that connects the leaf from the rest of the graph makes the leaf disconnected (!). Otherwise, define the following partition of $G$ without $e$:
$$G_u = (V_u, E_u) quad quad G_v = (V_v, E_v)$$
where $V_u = {w in V |$ there is a path from $w$ to $u$ that does not contain $e}$, $E_u = {(w, t) in E | w, t in V_u}$ and $V_v$, $E_v$ are defined analogously (2). If we remove $u$ or $v$ from the graph, then we are also removing $e$. Note, however, that if we remove $e$, then there is no path to go from any $w in G_u$ to any $t in G_v$. In other words, the graph becomes disconnected (!).
Notes:
(1) Suppose that there exists a path from $u$ to $v$ that does not contain $e$. Then we can join this path to $e$ to form a cycle, but by doing so we are showing that $e$ lies on a cycle (!).
(2) It is easy to show that $G_u$ and $G_v$ are disjoint.
answered 2 days ago
Just_a_newbie
526
edited yesterday
answered 2 days ago
Just_a_newbie
526
answered 2 days ago
Just_a_newbie
526
answered 2 days ago
Just_a_newbie
526
526
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005438%2fshow-any-two-edges-in-a-2-connected-graph-lie-on-a-cycle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure.
– Batominovski
2 days ago
@Batominovski Here I'm referring to 2-vertex-connected.
– Thomas
2 days ago