Given a simple graph and its complement, prove that either of them is always connected.Connectivity in graph...
Short story about cities being connected by a conveyor belt
3.5% Interest Student Loan or use all of my savings on Tuition?
Is every open circuit a capacitor?
Other authors are notified except me, good or bad sign?
Create chunks from an array
Giving a talk in my old university, how prominently should I tell students my salary?
Redunant indexes SQL Server
What is the orbital boost acceleration of the ISS?
Rationale to prefer local variables over instance variables?
How to write a chaotic neutral protagonist and prevent my readers from thinking they are evil?
Can a space-faring robot still function over a billion years?
Why do phishing e-mails use faked e-mail addresses instead of the real one?
Increase the space between numerator and denominator
Unfamiliar notation in Diabelli's "Duet in D" for piano
School performs periodic password audits. Is my password compromised?
Is there a math expression equivalent to the conditional ternary operator?
An Undercover Army
What is Tony Stark injecting into himself in Iron Man 3?
Is being socially reclusive okay for a graduate student?
Why aren't there more Gauls like Obelix?
A running toilet that stops itself
Has a sovereign Communist government ever run, and conceded loss, on a fair election?
What do I miss if I buy Monster Hunter: World late?
How does Sundering Titan handle snow lands?
Given a simple graph and its complement, prove that either of them is always connected.
Connectivity in graph theoryLet $G(V,E)$ be an un-directed, un-connected graph. Prove that $bar G$ is connected, And its Diameter is at most $2$.Prove that for any graph G, either G or its complement $bar{G}$ is connectedThe maximum no. of edges in a DISCONNECTED simple graph…Proving that a random graph is almost surely connectedComplement of G is connected.Help with induction question?How to prove that the complement of disconnected graph with $2$ vertices of even degree has a Eulerian path?Is the complement of a directed and not strongly connected graph connected?Proof that any simple connected graph has at least 2 non-cut vertices.Proof that for any graph, $|E| leq (|V| - k +1)(|V|-k)/2$Prove that for any graph G, either G or its complement $bar{G}$ is connectedMinimal graph such that the greedy pathing algorithm always terminatesLargest and least amount of connected components of graph with conditionsGraph Theory (Prove that a a simple graph and its complement cannot both be disconnected)Complement of a simple, connected graphPath length where almost every node has exactly two edges. Alternate formulation in terms of transpositions in symmetric group.If every $H$-free $2$-connected graph is Hamiltonian then $H$ is $P_3$Given a simple graph and its complement. Prove that either of them has a cycle.
$begingroup$
I was tasked to prove that when given 2 graphs $G$ and $bar{G}$ (complement), at least one of them is a always a connected graph.
Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with # of components, circuit ranks, etc, but to no avail.
So I really hope someone could give me a hint on how to approach this problem.
graph-theory
asked Mar 19 '12 at 18:42
ivtivt
73141023
$endgroup$
add a comment |
$begingroup$
I was tasked to prove that when given 2 graphs $G$ and $bar{G}$ (complement), at least one of them is a always a connected graph.
Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with # of components, circuit ranks, etc, but to no avail.
So I really hope someone could give me a hint on how to approach this problem.
graph-theory
asked Mar 19 '12 at 18:42
ivtivt
73141023
$endgroup$
add a comment |
$begingroup$
I was tasked to prove that when given 2 graphs $G$ and $bar{G}$ (complement), at least one of them is a always a connected graph.
Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with # of components, circuit ranks, etc, but to no avail.
So I really hope someone could give me a hint on how to approach this problem.
graph-theory
asked Mar 19 '12 at 18:42
ivtivt
73141023
$endgroup$
I was tasked to prove that when given 2 graphs $G$ and $bar{G}$ (complement), at least one of them is a always a connected graph.
Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with # of components, circuit ranks, etc, but to no avail.
So I really hope someone could give me a hint on how to approach this problem.
graph-theory
graph-theory
asked Mar 19 '12 at 18:42
ivtivt
73141023
asked Mar 19 '12 at 18:42
ivtivt
73141023
asked Mar 19 '12 at 18:42
ivtivt
73141023
asked Mar 19 '12 at 18:42
ivtivt
73141023
asked Mar 19 '12 at 18:42
ivtivt
73141023
73141023
add a comment |
add a comment |
7 Answers
7
active
oldest
votes
$begingroup$
Suppose $G$ is disconnected. We want to show that $bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $bar{G}$, and so we have a path from $v$ to $w$ in $bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $bar{G}$.
This shows that any two vertices in $bar{G}$ have a path (in fact a path of length one or two) between them in $bar{G}$, so $bar{G}$ is connected.
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
$endgroup$
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
2
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
3
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
add a comment |
$begingroup$
If $bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 in V_1$ and $v_2 in V_2$ we have $langle v_1,v_2rangle notin bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $langle v_1,v_2 rangle in E$, hence $G$ is connected.
I hope this helps ;-)
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
$endgroup$
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
3
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
add a comment |
$begingroup$
I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.
Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $overline G.$
Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $overline G.$
Let $H$ be the subgraph of $G$ induced by ${a,b,c,d},$ a graph with $2,3,$ or $4$ vertices depending on how ${a,b}$ and ${c,d}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $overline H$ are still disconnected.
Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!
Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the sum of two complete graphs. Up to $4$ vertices, the only graphs I have to check are:
$$K_1+K_1, K_1+K_2, K_1+K_3, K_2+K_2.$$
The complements of those graphs are
$$K_{1,1}, K_{1,2}, K_{1,3}, K_{2,2}.$$
The complements are all connected! That does it!!
Wait a minute, that's looking suspiciously similar to the proofs in the other answers.
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
Additionally, it will be easy if simply look at the adjacency matrix of the graph.
More explanation: The adjacency matrix of a disconnected graph will be block diagonal. Then think about its complement, if two vertices were in different connected component in the original graph, then they are adjacent in the complement; if two vertices were in the same connected component in the orginal graph, then a $2$-path connects them.
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
$endgroup$
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
add a comment |
$begingroup$
Suppose one of G = (V,E) and G' = (V,E) is disconnected; say G with components
G., . . . .,Gk, k > 1, w.l.o.g since G = G''. Any two vertices v∉Gi and w∉Gj will be
connected in G' since
(a) if i 6≠j then vw ∉ E, so vw 2 E'.
(b) if i = j then there must be a third vertex u in another component such that vu ∉ E and
wu ∉ E. In this case, v and w would be connected in G' through edges vu,wu ∉ E'.
Since any pair of vertices in G' are connected, G' is connected.
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
$endgroup$
add a comment |
$begingroup$
This is another answer, showing G¯ is connected in 3 cases by showing there exists an {a,b} path in each case. Let x,y be vertices in G. Let H be the component that holds the vertex x but not y.
C1: Suppose a and b are arbitrary vertices not in H. Then x~a and x~b in G¯ so there is a unique {a,b} path in G¯, namely {a,x,b}. (~ means adjacent)
C2: Suppose H holds one of the two vertices, a and b. Without loss of generality suppose H holds a. Then x~b and a~b in G¯. So there is a unique {a,b} path in G¯, namely {a,b}.
C3: Suppose H holds both the a and b vertices. Then y~a, y~b, y~x in G¯. So there is a unique {a,b} path in G¯, namely {a,y,b}.
Therefore there is a unique {a,b} path in G¯ for arbitrary a and b vertices in all 3 cases. Therefore G¯ is connected.
answered Apr 3 '17 at 11:14
DevinDevin
1
$endgroup$
1
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
add a comment |
$begingroup$
This can be done with induction.
- Show it is true for $n$ vertices
- And then prove it for $n+1$ vertices by considering $2$ cases:
$V_{n+1}$ is none off ${V_1,V_2,ldots,V_n}$
$V_{n+1}$ is connected to some of ${V_1, V_2,ldots, V_n}, it will never be connected to all because then the graph will be connected.
edited yesterday
Daniele Tampieri
2,3972922
answered yesterday
Sashin ChettySashin Chetty
113
$endgroup$
add a comment |
protected by Saad yesterday
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
7 Answers
7
active
oldest
votes
7 Answers
7
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose $G$ is disconnected. We want to show that $bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $bar{G}$, and so we have a path from $v$ to $w$ in $bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $bar{G}$.
This shows that any two vertices in $bar{G}$ have a path (in fact a path of length one or two) between them in $bar{G}$, so $bar{G}$ is connected.
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
$endgroup$
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
2
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
3
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
add a comment |
$begingroup$
Suppose $G$ is disconnected. We want to show that $bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $bar{G}$, and so we have a path from $v$ to $w$ in $bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $bar{G}$.
This shows that any two vertices in $bar{G}$ have a path (in fact a path of length one or two) between them in $bar{G}$, so $bar{G}$ is connected.
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
$endgroup$
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
2
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
3
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
add a comment |
$begingroup$
Suppose $G$ is disconnected. We want to show that $bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $bar{G}$, and so we have a path from $v$ to $w$ in $bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $bar{G}$.
This shows that any two vertices in $bar{G}$ have a path (in fact a path of length one or two) between them in $bar{G}$, so $bar{G}$ is connected.
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
$endgroup$
Suppose $G$ is disconnected. We want to show that $bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $bar{G}$, and so we have a path from $v$ to $w$ in $bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $bar{G}$.
This shows that any two vertices in $bar{G}$ have a path (in fact a path of length one or two) between them in $bar{G}$, so $bar{G}$ is connected.
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
answered Mar 19 '12 at 18:49
Chris EagleChris Eagle
29.2k27199
29.2k27199
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
2
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
3
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
add a comment |
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
2
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
3
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
$begingroup$
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted!
$endgroup$
– ivt
Mar 19 '12 at 19:01
2
2
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
$begingroup$
I wonder what we might point out here as a generally useful tactic?
$endgroup$
– MJD
Mar 19 '12 at 19:28
3
3
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
$begingroup$
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem.
$endgroup$
– ivt
Mar 19 '12 at 19:54
add a comment |
$begingroup$
If $bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 in V_1$ and $v_2 in V_2$ we have $langle v_1,v_2rangle notin bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $langle v_1,v_2 rangle in E$, hence $G$ is connected.
I hope this helps ;-)
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
$endgroup$
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
3
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
add a comment |
$begingroup$
If $bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 in V_1$ and $v_2 in V_2$ we have $langle v_1,v_2rangle notin bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $langle v_1,v_2 rangle in E$, hence $G$ is connected.
I hope this helps ;-)
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
$endgroup$
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
3
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
add a comment |
$begingroup$
If $bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 in V_1$ and $v_2 in V_2$ we have $langle v_1,v_2rangle notin bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $langle v_1,v_2 rangle in E$, hence $G$ is connected.
I hope this helps ;-)
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
$endgroup$
If $bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 in V_1$ and $v_2 in V_2$ we have $langle v_1,v_2rangle notin bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $langle v_1,v_2 rangle in E$, hence $G$ is connected.
I hope this helps ;-)
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
answered Mar 20 '13 at 9:20
dtldarekdtldarek
32.4k745100
32.4k745100
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
3
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
add a comment |
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
3
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
$begingroup$
Such a nice proof..
$endgroup$
– muzzlator
Mar 20 '13 at 9:50
3
3
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
$begingroup$
Would the downvoter care to explain?
$endgroup$
– dtldarek
Mar 21 '13 at 0:03
add a comment |
$begingroup$
I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.
Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $overline G.$
Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $overline G.$
Let $H$ be the subgraph of $G$ induced by ${a,b,c,d},$ a graph with $2,3,$ or $4$ vertices depending on how ${a,b}$ and ${c,d}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $overline H$ are still disconnected.
Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!
Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the sum of two complete graphs. Up to $4$ vertices, the only graphs I have to check are:
$$K_1+K_1, K_1+K_2, K_1+K_3, K_2+K_2.$$
The complements of those graphs are
$$K_{1,1}, K_{1,2}, K_{1,3}, K_{2,2}.$$
The complements are all connected! That does it!!
Wait a minute, that's looking suspiciously similar to the proofs in the other answers.
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.
Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $overline G.$
Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $overline G.$
Let $H$ be the subgraph of $G$ induced by ${a,b,c,d},$ a graph with $2,3,$ or $4$ vertices depending on how ${a,b}$ and ${c,d}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $overline H$ are still disconnected.
Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!
Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the sum of two complete graphs. Up to $4$ vertices, the only graphs I have to check are:
$$K_1+K_1, K_1+K_2, K_1+K_3, K_2+K_2.$$
The complements of those graphs are
$$K_{1,1}, K_{1,2}, K_{1,3}, K_{2,2}.$$
The complements are all connected! That does it!!
Wait a minute, that's looking suspiciously similar to the proofs in the other answers.
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
$endgroup$
add a comment |
$begingroup$
I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.
Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $overline G.$
Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $overline G.$
Let $H$ be the subgraph of $G$ induced by ${a,b,c,d},$ a graph with $2,3,$ or $4$ vertices depending on how ${a,b}$ and ${c,d}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $overline H$ are still disconnected.
Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!
Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the sum of two complete graphs. Up to $4$ vertices, the only graphs I have to check are:
$$K_1+K_1, K_1+K_2, K_1+K_3, K_2+K_2.$$
The complements of those graphs are
$$K_{1,1}, K_{1,2}, K_{1,3}, K_{2,2}.$$
The complements are all connected! That does it!!
Wait a minute, that's looking suspiciously similar to the proofs in the other answers.
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
$endgroup$
I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.
Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $overline G.$
Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $overline G.$
Let $H$ be the subgraph of $G$ induced by ${a,b,c,d},$ a graph with $2,3,$ or $4$ vertices depending on how ${a,b}$ and ${c,d}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $overline H$ are still disconnected.
Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!
Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the sum of two complete graphs. Up to $4$ vertices, the only graphs I have to check are:
$$K_1+K_1, K_1+K_2, K_1+K_3, K_2+K_2.$$
The complements of those graphs are
$$K_{1,1}, K_{1,2}, K_{1,3}, K_{2,2}.$$
The complements are all connected! That does it!!
Wait a minute, that's looking suspiciously similar to the proofs in the other answers.
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
answered Apr 3 '17 at 12:11
bofbof
52.3k558121
52.3k558121
add a comment |
add a comment |
$begingroup$
Additionally, it will be easy if simply look at the adjacency matrix of the graph.
More explanation: The adjacency matrix of a disconnected graph will be block diagonal. Then think about its complement, if two vertices were in different connected component in the original graph, then they are adjacent in the complement; if two vertices were in the same connected component in the orginal graph, then a $2$-path connects them.
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
$endgroup$
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
add a comment |
$begingroup$
Additionally, it will be easy if simply look at the adjacency matrix of the graph.
More explanation: The adjacency matrix of a disconnected graph will be block diagonal. Then think about its complement, if two vertices were in different connected component in the original graph, then they are adjacent in the complement; if two vertices were in the same connected component in the orginal graph, then a $2$-path connects them.
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
$endgroup$
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
add a comment |
$begingroup$
Additionally, it will be easy if simply look at the adjacency matrix of the graph.
More explanation: The adjacency matrix of a disconnected graph will be block diagonal. Then think about its complement, if two vertices were in different connected component in the original graph, then they are adjacent in the complement; if two vertices were in the same connected component in the orginal graph, then a $2$-path connects them.
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
$endgroup$
Additionally, it will be easy if simply look at the adjacency matrix of the graph.
More explanation: The adjacency matrix of a disconnected graph will be block diagonal. Then think about its complement, if two vertices were in different connected component in the original graph, then they are adjacent in the complement; if two vertices were in the same connected component in the orginal graph, then a $2$-path connects them.
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
edited Apr 19 '13 at 2:37
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
answered Apr 19 '13 at 2:13
EasyEasy
3,525917
3,525917
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
add a comment |
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
${}{}{}{}{}$How?
$endgroup$
– Aryabhata
Apr 19 '13 at 2:32
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
@Aryabhata, see my further explanation.
$endgroup$
– Easy
Apr 19 '13 at 2:36
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO).
$endgroup$
– Aryabhata
Apr 19 '13 at 3:24
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar.
$endgroup$
– Easy
Apr 19 '13 at 3:34
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
$begingroup$
You may be right. I didn't actually read Chris' answer :-)
$endgroup$
– Aryabhata
Apr 19 '13 at 4:23
add a comment |
$begingroup$
Suppose one of G = (V,E) and G' = (V,E) is disconnected; say G with components
G., . . . .,Gk, k > 1, w.l.o.g since G = G''. Any two vertices v∉Gi and w∉Gj will be
connected in G' since
(a) if i 6≠j then vw ∉ E, so vw 2 E'.
(b) if i = j then there must be a third vertex u in another component such that vu ∉ E and
wu ∉ E. In this case, v and w would be connected in G' through edges vu,wu ∉ E'.
Since any pair of vertices in G' are connected, G' is connected.
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
$endgroup$
add a comment |
$begingroup$
Suppose one of G = (V,E) and G' = (V,E) is disconnected; say G with components
G., . . . .,Gk, k > 1, w.l.o.g since G = G''. Any two vertices v∉Gi and w∉Gj will be
connected in G' since
(a) if i 6≠j then vw ∉ E, so vw 2 E'.
(b) if i = j then there must be a third vertex u in another component such that vu ∉ E and
wu ∉ E. In this case, v and w would be connected in G' through edges vu,wu ∉ E'.
Since any pair of vertices in G' are connected, G' is connected.
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
$endgroup$
add a comment |
$begingroup$
Suppose one of G = (V,E) and G' = (V,E) is disconnected; say G with components
G., . . . .,Gk, k > 1, w.l.o.g since G = G''. Any two vertices v∉Gi and w∉Gj will be
connected in G' since
(a) if i 6≠j then vw ∉ E, so vw 2 E'.
(b) if i = j then there must be a third vertex u in another component such that vu ∉ E and
wu ∉ E. In this case, v and w would be connected in G' through edges vu,wu ∉ E'.
Since any pair of vertices in G' are connected, G' is connected.
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
$endgroup$
Suppose one of G = (V,E) and G' = (V,E) is disconnected; say G with components
G., . . . .,Gk, k > 1, w.l.o.g since G = G''. Any two vertices v∉Gi and w∉Gj will be
connected in G' since
(a) if i 6≠j then vw ∉ E, so vw 2 E'.
(b) if i = j then there must be a third vertex u in another component such that vu ∉ E and
wu ∉ E. In this case, v and w would be connected in G' through edges vu,wu ∉ E'.
Since any pair of vertices in G' are connected, G' is connected.
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
answered Sep 15 '13 at 8:09
shamsu shehushamsu shehu
1
1
add a comment |
add a comment |
$begingroup$
This is another answer, showing G¯ is connected in 3 cases by showing there exists an {a,b} path in each case. Let x,y be vertices in G. Let H be the component that holds the vertex x but not y.
C1: Suppose a and b are arbitrary vertices not in H. Then x~a and x~b in G¯ so there is a unique {a,b} path in G¯, namely {a,x,b}. (~ means adjacent)
C2: Suppose H holds one of the two vertices, a and b. Without loss of generality suppose H holds a. Then x~b and a~b in G¯. So there is a unique {a,b} path in G¯, namely {a,b}.
C3: Suppose H holds both the a and b vertices. Then y~a, y~b, y~x in G¯. So there is a unique {a,b} path in G¯, namely {a,y,b}.
Therefore there is a unique {a,b} path in G¯ for arbitrary a and b vertices in all 3 cases. Therefore G¯ is connected.
answered Apr 3 '17 at 11:14
DevinDevin
1
$endgroup$
1
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
add a comment |
$begingroup$
This is another answer, showing G¯ is connected in 3 cases by showing there exists an {a,b} path in each case. Let x,y be vertices in G. Let H be the component that holds the vertex x but not y.
C1: Suppose a and b are arbitrary vertices not in H. Then x~a and x~b in G¯ so there is a unique {a,b} path in G¯, namely {a,x,b}. (~ means adjacent)
C2: Suppose H holds one of the two vertices, a and b. Without loss of generality suppose H holds a. Then x~b and a~b in G¯. So there is a unique {a,b} path in G¯, namely {a,b}.
C3: Suppose H holds both the a and b vertices. Then y~a, y~b, y~x in G¯. So there is a unique {a,b} path in G¯, namely {a,y,b}.
Therefore there is a unique {a,b} path in G¯ for arbitrary a and b vertices in all 3 cases. Therefore G¯ is connected.
answered Apr 3 '17 at 11:14
DevinDevin
1
$endgroup$
1
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
add a comment |
$begingroup$
This is another answer, showing G¯ is connected in 3 cases by showing there exists an {a,b} path in each case. Let x,y be vertices in G. Let H be the component that holds the vertex x but not y.
C1: Suppose a and b are arbitrary vertices not in H. Then x~a and x~b in G¯ so there is a unique {a,b} path in G¯, namely {a,x,b}. (~ means adjacent)
C2: Suppose H holds one of the two vertices, a and b. Without loss of generality suppose H holds a. Then x~b and a~b in G¯. So there is a unique {a,b} path in G¯, namely {a,b}.
C3: Suppose H holds both the a and b vertices. Then y~a, y~b, y~x in G¯. So there is a unique {a,b} path in G¯, namely {a,y,b}.
Therefore there is a unique {a,b} path in G¯ for arbitrary a and b vertices in all 3 cases. Therefore G¯ is connected.
answered Apr 3 '17 at 11:14
DevinDevin
1
$endgroup$
This is another answer, showing G¯ is connected in 3 cases by showing there exists an {a,b} path in each case. Let x,y be vertices in G. Let H be the component that holds the vertex x but not y.
C1: Suppose a and b are arbitrary vertices not in H. Then x~a and x~b in G¯ so there is a unique {a,b} path in G¯, namely {a,x,b}. (~ means adjacent)
C2: Suppose H holds one of the two vertices, a and b. Without loss of generality suppose H holds a. Then x~b and a~b in G¯. So there is a unique {a,b} path in G¯, namely {a,b}.
C3: Suppose H holds both the a and b vertices. Then y~a, y~b, y~x in G¯. So there is a unique {a,b} path in G¯, namely {a,y,b}.
Therefore there is a unique {a,b} path in G¯ for arbitrary a and b vertices in all 3 cases. Therefore G¯ is connected.
answered Apr 3 '17 at 11:14
DevinDevin
1
answered Apr 3 '17 at 11:14
DevinDevin
1
answered Apr 3 '17 at 11:14
DevinDevin
1
answered Apr 3 '17 at 11:14
DevinDevin
1
1
1
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
add a comment |
1
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
1
1
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
$begingroup$
Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
$endgroup$
– mlc
Apr 3 '17 at 11:24
add a comment |
$begingroup$
This can be done with induction.
- Show it is true for $n$ vertices
- And then prove it for $n+1$ vertices by considering $2$ cases:
$V_{n+1}$ is none off ${V_1,V_2,ldots,V_n}$
$V_{n+1}$ is connected to some of ${V_1, V_2,ldots, V_n}, it will never be connected to all because then the graph will be connected.
edited yesterday
Daniele Tampieri
2,3972922
answered yesterday
Sashin ChettySashin Chetty
113
$endgroup$
add a comment |
$begingroup$
This can be done with induction.
- Show it is true for $n$ vertices
- And then prove it for $n+1$ vertices by considering $2$ cases:
$V_{n+1}$ is none off ${V_1,V_2,ldots,V_n}$
$V_{n+1}$ is connected to some of ${V_1, V_2,ldots, V_n}, it will never be connected to all because then the graph will be connected.
edited yesterday
Daniele Tampieri
2,3972922
answered yesterday
Sashin ChettySashin Chetty
113
$endgroup$
add a comment |
$begingroup$
This can be done with induction.
- Show it is true for $n$ vertices
- And then prove it for $n+1$ vertices by considering $2$ cases:
$V_{n+1}$ is none off ${V_1,V_2,ldots,V_n}$
$V_{n+1}$ is connected to some of ${V_1, V_2,ldots, V_n}, it will never be connected to all because then the graph will be connected.
edited yesterday
Daniele Tampieri
2,3972922
answered yesterday
Sashin ChettySashin Chetty
113
$endgroup$
This can be done with induction.
- Show it is true for $n$ vertices
- And then prove it for $n+1$ vertices by considering $2$ cases:
$V_{n+1}$ is none off ${V_1,V_2,ldots,V_n}$
$V_{n+1}$ is connected to some of ${V_1, V_2,ldots, V_n}, it will never be connected to all because then the graph will be connected.
edited yesterday
Daniele Tampieri
2,3972922
answered yesterday
Sashin ChettySashin Chetty
113
edited yesterday
Daniele Tampieri
2,3972922
edited yesterday
Daniele Tampieri
2,3972922
edited yesterday
Daniele Tampieri
2,3972922
2,3972922
answered yesterday
Sashin ChettySashin Chetty
113
answered yesterday
Sashin ChettySashin Chetty
113
answered yesterday
Sashin ChettySashin Chetty
113
113
add a comment |
add a comment |
protected by Saad yesterday
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
