Theorem in graph theory about crossing numbers of $C_4 times C_4$ graph

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Consider first these definitions

Definition $1$. A drawing of a graph $G$ is optimal if it has the minimal number of possible crossings

Definition $2$.

For a subset $X$ of vertices of a graph $G$, $delta X$ is the set of edges of $G$ that are incident with both $X$ and $V(G)setminus X$.

Lemma $1$

Let $X$ be a subset of $V = V(Q_3)$. If $|X| geq 2$ and $|V(G)setminus X| geq 2$. Then $| delta X | geq 4$.

Lemma $2$

Let $v$ be a degree $4$ vertex in a graph $G$. In an optimal drawing
of $G$ there is no edge that crosses exactly three of the edges incident with $v$.

Definition $2$. In a simple drawing of a graph $G$, let $C$ be a cycle and let $H$ be a subgraph that is vertex-disjoint from $C$. We say that $C$ separates $H$ if there are vertices of $H$ in different regions of $C$. If at least $j$ vertices of $H$ are in different regions than at least $k$ other vertices of $H$, we say that $C$ separates $j$ from $k$ in $H$.

Now we need to prove this theorem using lemma $1$ and $2$.
Please let me understand the flow of the proof, it is much appreciated

Theorem $1$

In any optimal, simple drawing of $C_4 times C_4$ there is a $4$-cycle that is crossed at least four times.

begin proof..

Fix an optimal, simple drawing of $C_4 times C_4$, and let $e$ and $f$ be
two edges that cross in this drawing. Then we can find two disjoint copies
of $Q_3$, say $Q_e$, and $Q_f$, such that $e$ is in $Q_e$, and $f$ is in $Q_f$. Let $C_e$, denote a $4$-cycle in $Q_e$, containing the edge $e$; define $C_f$ similarly. We will color the vertices and edges of $Q_e$, green, the vertices and edges of $Q_f$ blue, and all other edges of $C_4 times C_4$ red.

If $C_e$, does not separate $f$, then $f$ must cross $C_e$, at least twice; the same is true if the roles of $e$ and $f$ are reversed. Thus if neither $C_e$, separates $f$ nor $C_f$, separates $e$, then both cycles are crossed at least four times and we are done. So assume without loss of generality that $C_e$, separates $f$.

Since $C_e$, separates $f$, it also separates $Q_f$. If $C_e$, separates $2$ from $2$ in $Q_f$,
then $C_e$, is crossed at least four times by Lemma $1$. So we may assume that one (blue) vertex $v$ of $Q_f$ is in one region of $C_e$, and the remaining seven are in another. It follows that $C_e$, has at least three crossings (the three blue edges incident with the vertex $u$). If $C_e$, has four crossings we are done, so we may assume that the remaining (red) edge incident with u does not cross $C_e$, we may assume that $C_e$, does not cross itself, and finally we may assume that each of the blue edges crossing $C_e$, does so only once. Call these blue edges $f_l$, $f_2$, and $f_3$, and consider which edges of $C_e$, might be crossed by these three edges.

If two of these edges cross opposite edges of $C_e$, then the unique $4$-cycle they determine in $Q_r$ separates $2$ vertices from $2$ in $Q_e$, and so this $4$-cycle would have four crossings by Lemma $1$. If all three edges cross $e$, then by Lemma $2$ the fourth $u$-incident edge would cross $e$ as well. Thus the only possible arrangement is the one shown in Figure $2$, where we assume that $f_l$ and $f_2$ cross a common edge of $C_e$.

Consider the two blue $4$-cycles in $Q_f$ determined, respectively, by the
edges $f_1$ and $f_3$ and by the edges $f_2$ and $f_3$. If neither cycle has four crossings, then neither cycle crosses itself and the two cycles do not cross each other. Also, if neither of these cycles is to have four crossings, then each must separate $1$ from $7$ in $Q_e$; this gives three green crossings for each of the two blue cycles. Furthermore, in each case the one vertex that is separated from the other seven in $Q_e$, must be the vertex incident with the two crossed edges of $C_e$; call this vertex $u$.

By considering whether the green vertex $u$ is inside or outside each blue $4$-cycle, we obtain three possible cases, shown in Figure $3$. We use $x$ and $y$ to denote the vertices on the $f_2-f_3$ $4$-cycle that are not incident with the edge $f_3$.

In each of these cases the $f_1-f_3$ cycle separates $x$, $y$, and $u$ from the other seven green vertices. Hence this cycle is crossed by least three green edges (from $u$) and at least one red edge (from $x$ and/or $y$)

end of proof....

combinatorics graph-theory graphing-functions algebraic-graph-theory extremal-graph-theory

share|cite|improve this question

edited Jul 28 at 16:35

Daniel Buck

2,2841623

asked Jul 28 at 13:26

Xanderfort

186

add a comment | 

up vote
0
down vote

favorite

Consider first these definitions

Definition $1$. A drawing of a graph $G$ is optimal if it has the minimal number of possible crossings

Definition $2$.

For a subset $X$ of vertices of a graph $G$, $delta X$ is the set of edges of $G$ that are incident with both $X$ and $V(G)setminus X$.

Lemma $1$

Let $X$ be a subset of $V = V(Q_3)$. If $|X| geq 2$ and $|V(G)setminus X| geq 2$. Then $| delta X | geq 4$.

Lemma $2$

Let $v$ be a degree $4$ vertex in a graph $G$. In an optimal drawing
of $G$ there is no edge that crosses exactly three of the edges incident with $v$.

Definition $2$. In a simple drawing of a graph $G$, let $C$ be a cycle and let $H$ be a subgraph that is vertex-disjoint from $C$. We say that $C$ separates $H$ if there are vertices of $H$ in different regions of $C$. If at least $j$ vertices of $H$ are in different regions than at least $k$ other vertices of $H$, we say that $C$ separates $j$ from $k$ in $H$.

Now we need to prove this theorem using lemma $1$ and $2$.
Please let me understand the flow of the proof, it is much appreciated

Theorem $1$

In any optimal, simple drawing of $C_4 times C_4$ there is a $4$-cycle that is crossed at least four times.

begin proof..

Fix an optimal, simple drawing of $C_4 times C_4$, and let $e$ and $f$ be
two edges that cross in this drawing. Then we can find two disjoint copies
of $Q_3$, say $Q_e$, and $Q_f$, such that $e$ is in $Q_e$, and $f$ is in $Q_f$. Let $C_e$, denote a $4$-cycle in $Q_e$, containing the edge $e$; define $C_f$ similarly. We will color the vertices and edges of $Q_e$, green, the vertices and edges of $Q_f$ blue, and all other edges of $C_4 times C_4$ red.

If $C_e$, does not separate $f$, then $f$ must cross $C_e$, at least twice; the same is true if the roles of $e$ and $f$ are reversed. Thus if neither $C_e$, separates $f$ nor $C_f$, separates $e$, then both cycles are crossed at least four times and we are done. So assume without loss of generality that $C_e$, separates $f$.

Since $C_e$, separates $f$, it also separates $Q_f$. If $C_e$, separates $2$ from $2$ in $Q_f$,
then $C_e$, is crossed at least four times by Lemma $1$. So we may assume that one (blue) vertex $v$ of $Q_f$ is in one region of $C_e$, and the remaining seven are in another. It follows that $C_e$, has at least three crossings (the three blue edges incident with the vertex $u$). If $C_e$, has four crossings we are done, so we may assume that the remaining (red) edge incident with u does not cross $C_e$, we may assume that $C_e$, does not cross itself, and finally we may assume that each of the blue edges crossing $C_e$, does so only once. Call these blue edges $f_l$, $f_2$, and $f_3$, and consider which edges of $C_e$, might be crossed by these three edges.

If two of these edges cross opposite edges of $C_e$, then the unique $4$-cycle they determine in $Q_r$ separates $2$ vertices from $2$ in $Q_e$, and so this $4$-cycle would have four crossings by Lemma $1$. If all three edges cross $e$, then by Lemma $2$ the fourth $u$-incident edge would cross $e$ as well. Thus the only possible arrangement is the one shown in Figure $2$, where we assume that $f_l$ and $f_2$ cross a common edge of $C_e$.

Consider the two blue $4$-cycles in $Q_f$ determined, respectively, by the
edges $f_1$ and $f_3$ and by the edges $f_2$ and $f_3$. If neither cycle has four crossings, then neither cycle crosses itself and the two cycles do not cross each other. Also, if neither of these cycles is to have four crossings, then each must separate $1$ from $7$ in $Q_e$; this gives three green crossings for each of the two blue cycles. Furthermore, in each case the one vertex that is separated from the other seven in $Q_e$, must be the vertex incident with the two crossed edges of $C_e$; call this vertex $u$.

By considering whether the green vertex $u$ is inside or outside each blue $4$-cycle, we obtain three possible cases, shown in Figure $3$. We use $x$ and $y$ to denote the vertices on the $f_2-f_3$ $4$-cycle that are not incident with the edge $f_3$.

In each of these cases the $f_1-f_3$ cycle separates $x$, $y$, and $u$ from the other seven green vertices. Hence this cycle is crossed by least three green edges (from $u$) and at least one red edge (from $x$ and/or $y$)

end of proof....

combinatorics graph-theory graphing-functions algebraic-graph-theory extremal-graph-theory

share|cite|improve this question

edited Jul 28 at 16:35

Daniel Buck

2,2841623

asked Jul 28 at 13:26

Xanderfort

186

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Consider first these definitions

Definition $1$. A drawing of a graph $G$ is optimal if it has the minimal number of possible crossings

Definition $2$.

For a subset $X$ of vertices of a graph $G$, $delta X$ is the set of edges of $G$ that are incident with both $X$ and $V(G)setminus X$.

Lemma $1$

Let $X$ be a subset of $V = V(Q_3)$. If $|X| geq 2$ and $|V(G)setminus X| geq 2$. Then $| delta X | geq 4$.

Lemma $2$

Let $v$ be a degree $4$ vertex in a graph $G$. In an optimal drawing
of $G$ there is no edge that crosses exactly three of the edges incident with $v$.

Definition $2$. In a simple drawing of a graph $G$, let $C$ be a cycle and let $H$ be a subgraph that is vertex-disjoint from $C$. We say that $C$ separates $H$ if there are vertices of $H$ in different regions of $C$. If at least $j$ vertices of $H$ are in different regions than at least $k$ other vertices of $H$, we say that $C$ separates $j$ from $k$ in $H$.

Now we need to prove this theorem using lemma $1$ and $2$.
Please let me understand the flow of the proof, it is much appreciated

Theorem $1$

In any optimal, simple drawing of $C_4 times C_4$ there is a $4$-cycle that is crossed at least four times.

begin proof..

Fix an optimal, simple drawing of $C_4 times C_4$, and let $e$ and $f$ be
two edges that cross in this drawing. Then we can find two disjoint copies
of $Q_3$, say $Q_e$, and $Q_f$, such that $e$ is in $Q_e$, and $f$ is in $Q_f$. Let $C_e$, denote a $4$-cycle in $Q_e$, containing the edge $e$; define $C_f$ similarly. We will color the vertices and edges of $Q_e$, green, the vertices and edges of $Q_f$ blue, and all other edges of $C_4 times C_4$ red.

If $C_e$, does not separate $f$, then $f$ must cross $C_e$, at least twice; the same is true if the roles of $e$ and $f$ are reversed. Thus if neither $C_e$, separates $f$ nor $C_f$, separates $e$, then both cycles are crossed at least four times and we are done. So assume without loss of generality that $C_e$, separates $f$.

Since $C_e$, separates $f$, it also separates $Q_f$. If $C_e$, separates $2$ from $2$ in $Q_f$,
then $C_e$, is crossed at least four times by Lemma $1$. So we may assume that one (blue) vertex $v$ of $Q_f$ is in one region of $C_e$, and the remaining seven are in another. It follows that $C_e$, has at least three crossings (the three blue edges incident with the vertex $u$). If $C_e$, has four crossings we are done, so we may assume that the remaining (red) edge incident with u does not cross $C_e$, we may assume that $C_e$, does not cross itself, and finally we may assume that each of the blue edges crossing $C_e$, does so only once. Call these blue edges $f_l$, $f_2$, and $f_3$, and consider which edges of $C_e$, might be crossed by these three edges.

If two of these edges cross opposite edges of $C_e$, then the unique $4$-cycle they determine in $Q_r$ separates $2$ vertices from $2$ in $Q_e$, and so this $4$-cycle would have four crossings by Lemma $1$. If all three edges cross $e$, then by Lemma $2$ the fourth $u$-incident edge would cross $e$ as well. Thus the only possible arrangement is the one shown in Figure $2$, where we assume that $f_l$ and $f_2$ cross a common edge of $C_e$.

Consider the two blue $4$-cycles in $Q_f$ determined, respectively, by the
edges $f_1$ and $f_3$ and by the edges $f_2$ and $f_3$. If neither cycle has four crossings, then neither cycle crosses itself and the two cycles do not cross each other. Also, if neither of these cycles is to have four crossings, then each must separate $1$ from $7$ in $Q_e$; this gives three green crossings for each of the two blue cycles. Furthermore, in each case the one vertex that is separated from the other seven in $Q_e$, must be the vertex incident with the two crossed edges of $C_e$; call this vertex $u$.

By considering whether the green vertex $u$ is inside or outside each blue $4$-cycle, we obtain three possible cases, shown in Figure $3$. We use $x$ and $y$ to denote the vertices on the $f_2-f_3$ $4$-cycle that are not incident with the edge $f_3$.

In each of these cases the $f_1-f_3$ cycle separates $x$, $y$, and $u$ from the other seven green vertices. Hence this cycle is crossed by least three green edges (from $u$) and at least one red edge (from $x$ and/or $y$)

end of proof....

combinatorics graph-theory graphing-functions algebraic-graph-theory extremal-graph-theory

share|cite|improve this question

edited Jul 28 at 16:35

Daniel Buck

2,2841623

asked Jul 28 at 13:26

Xanderfort

186

Consider first these definitions

Definition $1$. A drawing of a graph $G$ is optimal if it has the minimal number of possible crossings

Definition $2$.

For a subset $X$ of vertices of a graph $G$, $delta X$ is the set of edges of $G$ that are incident with both $X$ and $V(G)setminus X$.

Lemma $1$

Let $X$ be a subset of $V = V(Q_3)$. If $|X| geq 2$ and $|V(G)setminus X| geq 2$. Then $| delta X | geq 4$.

Lemma $2$

Let $v$ be a degree $4$ vertex in a graph $G$. In an optimal drawing
of $G$ there is no edge that crosses exactly three of the edges incident with $v$.

Definition $2$. In a simple drawing of a graph $G$, let $C$ be a cycle and let $H$ be a subgraph that is vertex-disjoint from $C$. We say that $C$ separates $H$ if there are vertices of $H$ in different regions of $C$. If at least $j$ vertices of $H$ are in different regions than at least $k$ other vertices of $H$, we say that $C$ separates $j$ from $k$ in $H$.

Now we need to prove this theorem using lemma $1$ and $2$.
Please let me understand the flow of the proof, it is much appreciated

Theorem $1$

In any optimal, simple drawing of $C_4 times C_4$ there is a $4$-cycle that is crossed at least four times.

begin proof..

Fix an optimal, simple drawing of $C_4 times C_4$, and let $e$ and $f$ be
two edges that cross in this drawing. Then we can find two disjoint copies
of $Q_3$, say $Q_e$, and $Q_f$, such that $e$ is in $Q_e$, and $f$ is in $Q_f$. Let $C_e$, denote a $4$-cycle in $Q_e$, containing the edge $e$; define $C_f$ similarly. We will color the vertices and edges of $Q_e$, green, the vertices and edges of $Q_f$ blue, and all other edges of $C_4 times C_4$ red.

If $C_e$, does not separate $f$, then $f$ must cross $C_e$, at least twice; the same is true if the roles of $e$ and $f$ are reversed. Thus if neither $C_e$, separates $f$ nor $C_f$, separates $e$, then both cycles are crossed at least four times and we are done. So assume without loss of generality that $C_e$, separates $f$.

Since $C_e$, separates $f$, it also separates $Q_f$. If $C_e$, separates $2$ from $2$ in $Q_f$,
then $C_e$, is crossed at least four times by Lemma $1$. So we may assume that one (blue) vertex $v$ of $Q_f$ is in one region of $C_e$, and the remaining seven are in another. It follows that $C_e$, has at least three crossings (the three blue edges incident with the vertex $u$). If $C_e$, has four crossings we are done, so we may assume that the remaining (red) edge incident with u does not cross $C_e$, we may assume that $C_e$, does not cross itself, and finally we may assume that each of the blue edges crossing $C_e$, does so only once. Call these blue edges $f_l$, $f_2$, and $f_3$, and consider which edges of $C_e$, might be crossed by these three edges.

If two of these edges cross opposite edges of $C_e$, then the unique $4$-cycle they determine in $Q_r$ separates $2$ vertices from $2$ in $Q_e$, and so this $4$-cycle would have four crossings by Lemma $1$. If all three edges cross $e$, then by Lemma $2$ the fourth $u$-incident edge would cross $e$ as well. Thus the only possible arrangement is the one shown in Figure $2$, where we assume that $f_l$ and $f_2$ cross a common edge of $C_e$.

Consider the two blue $4$-cycles in $Q_f$ determined, respectively, by the
edges $f_1$ and $f_3$ and by the edges $f_2$ and $f_3$. If neither cycle has four crossings, then neither cycle crosses itself and the two cycles do not cross each other. Also, if neither of these cycles is to have four crossings, then each must separate $1$ from $7$ in $Q_e$; this gives three green crossings for each of the two blue cycles. Furthermore, in each case the one vertex that is separated from the other seven in $Q_e$, must be the vertex incident with the two crossed edges of $C_e$; call this vertex $u$.

By considering whether the green vertex $u$ is inside or outside each blue $4$-cycle, we obtain three possible cases, shown in Figure $3$. We use $x$ and $y$ to denote the vertices on the $f_2-f_3$ $4$-cycle that are not incident with the edge $f_3$.

In each of these cases the $f_1-f_3$ cycle separates $x$, $y$, and $u$ from the other seven green vertices. Hence this cycle is crossed by least three green edges (from $u$) and at least one red edge (from $x$ and/or $y$)

end of proof....

combinatorics graph-theory graphing-functions algebraic-graph-theory extremal-graph-theory

share|cite|improve this question

edited Jul 28 at 16:35

Daniel Buck

2,2841623

asked Jul 28 at 13:26

Xanderfort

186

share|cite|improve this question

share|cite|improve this question

edited Jul 28 at 16:35

Daniel Buck

2,2841623

edited Jul 28 at 16:35

Daniel Buck

2,2841623

edited Jul 28 at 16:35

Daniel Buck

2,2841623

2,2841623

asked Jul 28 at 13:26

Xanderfort

186

asked Jul 28 at 13:26

Xanderfort

186

asked Jul 28 at 13:26

Xanderfort

186

186

add a comment | 

add a comment | 

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865248%2ftheorem-in-graph-theory-about-crossing-numbers-of-c-4-times-c-4-graph%23new-answer', 'question_page');

);

Post as a guest

Name Email

active

oldest

votes

active

oldest

votes

active

oldest

votes

active

oldest

votes

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2865248%2ftheorem-in-graph-theory-about-crossing-numbers-of-c-4-times-c-4-graph%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Name Email

Name Email

Name

Email

Name Email

Name

Email