Mixing
$6$-regular graph of order $25$ and diameter $2$
$begingroup$
Is there a $6$-regular graph of order $25$ and diameter $2$?
According to this answer to a related problem, for any $r$-regular graph of order $n$ and diameter $2$, one must have $nleq r^2+1$.
When $n=25$, it follows that $r geq 5$ and since $r$ must be even (the sum of the degrees must be even), it follows that $rgeq 6$.
I was able to build a $8$-regular graph, but not a $6$-regular graph. Is there such a construction?
graph-theory extremal-graph-theory
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
$endgroup$
add a comment |
$begingroup$
Is there a $6$-regular graph of order $25$ and diameter $2$?
According to this answer to a related problem, for any $r$-regular graph of order $n$ and diameter $2$, one must have $nleq r^2+1$.
When $n=25$, it follows that $r geq 5$ and since $r$ must be even (the sum of the degrees must be even), it follows that $rgeq 6$.
I was able to build a $8$-regular graph, but not a $6$-regular graph. Is there such a construction?
graph-theory extremal-graph-theory
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
$endgroup$
add a comment |
$begingroup$
Is there a $6$-regular graph of order $25$ and diameter $2$?
According to this answer to a related problem, for any $r$-regular graph of order $n$ and diameter $2$, one must have $nleq r^2+1$.
When $n=25$, it follows that $r geq 5$ and since $r$ must be even (the sum of the degrees must be even), it follows that $rgeq 6$.
I was able to build a $8$-regular graph, but not a $6$-regular graph. Is there such a construction?
graph-theory extremal-graph-theory
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
$endgroup$
Is there a $6$-regular graph of order $25$ and diameter $2$?
According to this answer to a related problem, for any $r$-regular graph of order $n$ and diameter $2$, one must have $nleq r^2+1$.
When $n=25$, it follows that $r geq 5$ and since $r$ must be even (the sum of the degrees must be even), it follows that $rgeq 6$.
I was able to build a $8$-regular graph, but not a $6$-regular graph. Is there such a construction?
graph-theory extremal-graph-theory
graph-theory extremal-graph-theory
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
asked Feb 24 '18 at 19:18
digital-Inkdigital-Ink
904724
904724
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I know I've seen something like this before - an old Vietnamese olympiad problem, maybe? Then again, I don't recall the exact statement, so that doesn't actually help me.
We just kind of have to get down and grubby with this one. With so much space to give - twelve redundant paths per vertex - there isn't any great symmetry to work with. Anyway, here's an explicit construction:
Group our $25$ vertices into three subsets $A,B,C$, of size $10,$ $10,$ and $5$. Those sets will have internal graphs that are two Petersen graphs (3-regular) and a pentagon (2-regular). Then, each vertex in $A$ will have edges to two vertices in $B$ and one in $C$ (total degree $3+2+1=6$), each vertex in $B$ will have edges to two vertices in $A$ and one in $C$ (total degree $3+2+1=6$), and each vertex in $C$ will have edges to two vertices in $A$ and two in $B$ (total degree $2+2+2=6$).
Label the vertices of $A$ and $B$ with pairs $[a,x]$ as shown:
![[Figure 1]](https://i.stack.imgur.com/qcUgw.png)
Each $[O,x]$ has edges to $[O,x+1]$, $[O,x+2]$, and $[I,x]$. Each $[I,x]$ has edges to $[I,x+2]$, $[I,x-2]$, and $[O,x]$. The indices $x$ are, of course, interpreted mod $5$.
Label the vertices of the pentagon $C$ with a single index $[x]$, interpreted mod $5$. The internal edges of $C$ will go from $[x]$ to $[x+1]$ and $[x-1]$.
As is well-known, the pentagon and the Petersen graph each have diameter $2$. With just these edges, we have paths of length at most $2$ whenever our endpoints are in the same subset.
Now, we bring in the edges that cross boundaries. From $A$ to $C$, connect $[O,x]$ to $[2x]$ and $[I,x]$ to $[x]$. Starting at $[O,x]$, we can reach $[2x]$ in one step, then $[2x+1]$ and $[2x-1]$ in another step using the internal edges of $C$. Alternately, we can move to $[O,x+1]$ and then cross to $[2x+2]$ or move to $[O,x-1]$ and then cross to $[2x-2]$. That's all five vertices of $C$ reachable in two steps from an outer vertex of $A$.
From an inner vertex $[I,x]$ of $A$, we can cross to $[x]$ then step to $[x+1]$ or $[x-1]$, step to $[I,x+2]$ and cross to $[x+2]$, or step to $[I,x-2]$ and cross to $[x-2]$. Again, that's all five vertices of $C$ accounted for. Combine the two, and we can go from anywhere in $A$ to anywhere in $C$ in at most two steps. Of course, going from $C$ to $A$ just requires us to use the same path in reverse.
Between $B$ and $C$, add edges with the exact same indices that we had between $A$ and $C$. By the same proof, we then have paths of length at most $2$ between any point in $B$ and any point in $C$.
That just leaves paths between $A$ and $B$, the most complicated case. We add crossing edges as follows: from $[O,x]_A$ to $[O,2x]_B$, from $[O,x]_A$ to $[I,x]_B$, from $[I,x]_A$ to $[I,-2x]_B$, and from $[I,x]_A$ to $[O,-x]_B$.
A chart for the paths:
$$begin{array}{ccc|ccc}text{Start}&text{Step 1}&text{Step 2}&text{Start}&text{Step 1}&text{Step 2}\
hline [O,x]_A&[O,x+1]_A&[O,2x+2]_B&[I,x]_A&[I,x+2]_A&[I,-2x+1]_B\ [O,x]_A&[O,x+1]_A&[I,x+1]_B&[I,x]_A&[I,x+2]_A&[O,-x-2]_B\ [O,x]_A&[O,2x]_B&&[I,x]_A&[I,-2x]_B&\ [O,x]_A&[O,2x]_B&[O,2x+1]_B&[I,x]_A&[I,-2x]_B&[I,-2x+2]_B\ [O,x]_A&[O,2x]_B&[O,2x-1]_B&[I,x]_A&[I,-2x]_B&[I,-2x-2]_B\ [O,x]_A&[I,x]_B&&[I,x]_A&[O,-x]_B&\ [O,x]_A&[I,x]_B&[I,x+2]_B&[I,x]_A&[O,-x]_B&[O,-x+1]_B\ [O,x]_A&[I,x]_B&[I,x-2]_B&[I,x]_A&[O,-x]_B&[O,-x-1]_B\ [O,x]_A&[O,x-1]_A&[O,2x-2]_B&[I,x]_A&[I,x-2]_A&[I,-2x-1]_B\ [O,x]_A&[O,x-1]_A&[I,x-1]_B&[I,x]_A&[I,x-2]_A&[O,-x+2]_B
end{array}$$
That's all ten possibilities in $B$ accounted for, from a start at either an outer vertex or an inner vertex in $A$. We have explicitly constructed paths of length at most $2$ between any two points.
Many pairs of points, of course, have other paths between them. For example, we can go from $[O,0]$ in $A$ to $[0]$ in $C$ and then to $[O,0]$ in $B$, instead of taking the direct edge. These extra paths don't always play nicely with the mod 5 structure we're using, so it's not obvious at a glance how many triangles and quadrilaterals there are. Still, extra paths aren't actually a problem; all we needed here was at least one.
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
$endgroup$
add a comment |
Your Answer
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f2665019%2f6-regular-graph-of-order-25-and-diameter-2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I know I've seen something like this before - an old Vietnamese olympiad problem, maybe? Then again, I don't recall the exact statement, so that doesn't actually help me.
We just kind of have to get down and grubby with this one. With so much space to give - twelve redundant paths per vertex - there isn't any great symmetry to work with. Anyway, here's an explicit construction:
Group our $25$ vertices into three subsets $A,B,C$, of size $10,$ $10,$ and $5$. Those sets will have internal graphs that are two Petersen graphs (3-regular) and a pentagon (2-regular). Then, each vertex in $A$ will have edges to two vertices in $B$ and one in $C$ (total degree $3+2+1=6$), each vertex in $B$ will have edges to two vertices in $A$ and one in $C$ (total degree $3+2+1=6$), and each vertex in $C$ will have edges to two vertices in $A$ and two in $B$ (total degree $2+2+2=6$).
Label the vertices of $A$ and $B$ with pairs $[a,x]$ as shown:
Each $[O,x]$ has edges to $[O,x+1]$, $[O,x+2]$, and $[I,x]$. Each $[I,x]$ has edges to $[I,x+2]$, $[I,x-2]$, and $[O,x]$. The indices $x$ are, of course, interpreted mod $5$.
Label the vertices of the pentagon $C$ with a single index $[x]$, interpreted mod $5$. The internal edges of $C$ will go from $[x]$ to $[x+1]$ and $[x-1]$.
As is well-known, the pentagon and the Petersen graph each have diameter $2$. With just these edges, we have paths of length at most $2$ whenever our endpoints are in the same subset.
Now, we bring in the edges that cross boundaries. From $A$ to $C$, connect $[O,x]$ to $[2x]$ and $[I,x]$ to $[x]$. Starting at $[O,x]$, we can reach $[2x]$ in one step, then $[2x+1]$ and $[2x-1]$ in another step using the internal edges of $C$. Alternately, we can move to $[O,x+1]$ and then cross to $[2x+2]$ or move to $[O,x-1]$ and then cross to $[2x-2]$. That's all five vertices of $C$ reachable in two steps from an outer vertex of $A$.
From an inner vertex $[I,x]$ of $A$, we can cross to $[x]$ then step to $[x+1]$ or $[x-1]$, step to $[I,x+2]$ and cross to $[x+2]$, or step to $[I,x-2]$ and cross to $[x-2]$. Again, that's all five vertices of $C$ accounted for. Combine the two, and we can go from anywhere in $A$ to anywhere in $C$ in at most two steps. Of course, going from $C$ to $A$ just requires us to use the same path in reverse.
Between $B$ and $C$, add edges with the exact same indices that we had between $A$ and $C$. By the same proof, we then have paths of length at most $2$ between any point in $B$ and any point in $C$.
That just leaves paths between $A$ and $B$, the most complicated case. We add crossing edges as follows: from $[O,x]_A$ to $[O,2x]_B$, from $[O,x]_A$ to $[I,x]_B$, from $[I,x]_A$ to $[I,-2x]_B$, and from $[I,x]_A$ to $[O,-x]_B$.
A chart for the paths:
$$begin{array}{ccc|ccc}text{Start}&text{Step 1}&text{Step 2}&text{Start}&text{Step 1}&text{Step 2}\
hline [O,x]_A&[O,x+1]_A&[O,2x+2]_B&[I,x]_A&[I,x+2]_A&[I,-2x+1]_B\ [O,x]_A&[O,x+1]_A&[I,x+1]_B&[I,x]_A&[I,x+2]_A&[O,-x-2]_B\ [O,x]_A&[O,2x]_B&&[I,x]_A&[I,-2x]_B&\ [O,x]_A&[O,2x]_B&[O,2x+1]_B&[I,x]_A&[I,-2x]_B&[I,-2x+2]_B\ [O,x]_A&[O,2x]_B&[O,2x-1]_B&[I,x]_A&[I,-2x]_B&[I,-2x-2]_B\ [O,x]_A&[I,x]_B&&[I,x]_A&[O,-x]_B&\ [O,x]_A&[I,x]_B&[I,x+2]_B&[I,x]_A&[O,-x]_B&[O,-x+1]_B\ [O,x]_A&[I,x]_B&[I,x-2]_B&[I,x]_A&[O,-x]_B&[O,-x-1]_B\ [O,x]_A&[O,x-1]_A&[O,2x-2]_B&[I,x]_A&[I,x-2]_A&[I,-2x-1]_B\ [O,x]_A&[O,x-1]_A&[I,x-1]_B&[I,x]_A&[I,x-2]_A&[O,-x+2]_B
end{array}$$
That's all ten possibilities in $B$ accounted for, from a start at either an outer vertex or an inner vertex in $A$. We have explicitly constructed paths of length at most $2$ between any two points.
Many pairs of points, of course, have other paths between them. For example, we can go from $[O,0]$ in $A$ to $[0]$ in $C$ and then to $[O,0]$ in $B$, instead of taking the direct edge. These extra paths don't always play nicely with the mod 5 structure we're using, so it's not obvious at a glance how many triangles and quadrilaterals there are. Still, extra paths aren't actually a problem; all we needed here was at least one.
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
$endgroup$
add a comment |
$begingroup$
I know I've seen something like this before - an old Vietnamese olympiad problem, maybe? Then again, I don't recall the exact statement, so that doesn't actually help me.
We just kind of have to get down and grubby with this one. With so much space to give - twelve redundant paths per vertex - there isn't any great symmetry to work with. Anyway, here's an explicit construction:
Group our $25$ vertices into three subsets $A,B,C$, of size $10,$ $10,$ and $5$. Those sets will have internal graphs that are two Petersen graphs (3-regular) and a pentagon (2-regular). Then, each vertex in $A$ will have edges to two vertices in $B$ and one in $C$ (total degree $3+2+1=6$), each vertex in $B$ will have edges to two vertices in $A$ and one in $C$ (total degree $3+2+1=6$), and each vertex in $C$ will have edges to two vertices in $A$ and two in $B$ (total degree $2+2+2=6$).
Label the vertices of $A$ and $B$ with pairs $[a,x]$ as shown:
Each $[O,x]$ has edges to $[O,x+1]$, $[O,x+2]$, and $[I,x]$. Each $[I,x]$ has edges to $[I,x+2]$, $[I,x-2]$, and $[O,x]$. The indices $x$ are, of course, interpreted mod $5$.
Label the vertices of the pentagon $C$ with a single index $[x]$, interpreted mod $5$. The internal edges of $C$ will go from $[x]$ to $[x+1]$ and $[x-1]$.
As is well-known, the pentagon and the Petersen graph each have diameter $2$. With just these edges, we have paths of length at most $2$ whenever our endpoints are in the same subset.
Now, we bring in the edges that cross boundaries. From $A$ to $C$, connect $[O,x]$ to $[2x]$ and $[I,x]$ to $[x]$. Starting at $[O,x]$, we can reach $[2x]$ in one step, then $[2x+1]$ and $[2x-1]$ in another step using the internal edges of $C$. Alternately, we can move to $[O,x+1]$ and then cross to $[2x+2]$ or move to $[O,x-1]$ and then cross to $[2x-2]$. That's all five vertices of $C$ reachable in two steps from an outer vertex of $A$.
From an inner vertex $[I,x]$ of $A$, we can cross to $[x]$ then step to $[x+1]$ or $[x-1]$, step to $[I,x+2]$ and cross to $[x+2]$, or step to $[I,x-2]$ and cross to $[x-2]$. Again, that's all five vertices of $C$ accounted for. Combine the two, and we can go from anywhere in $A$ to anywhere in $C$ in at most two steps. Of course, going from $C$ to $A$ just requires us to use the same path in reverse.
Between $B$ and $C$, add edges with the exact same indices that we had between $A$ and $C$. By the same proof, we then have paths of length at most $2$ between any point in $B$ and any point in $C$.
That just leaves paths between $A$ and $B$, the most complicated case. We add crossing edges as follows: from $[O,x]_A$ to $[O,2x]_B$, from $[O,x]_A$ to $[I,x]_B$, from $[I,x]_A$ to $[I,-2x]_B$, and from $[I,x]_A$ to $[O,-x]_B$.
A chart for the paths:
$$begin{array}{ccc|ccc}text{Start}&text{Step 1}&text{Step 2}&text{Start}&text{Step 1}&text{Step 2}\
hline [O,x]_A&[O,x+1]_A&[O,2x+2]_B&[I,x]_A&[I,x+2]_A&[I,-2x+1]_B\ [O,x]_A&[O,x+1]_A&[I,x+1]_B&[I,x]_A&[I,x+2]_A&[O,-x-2]_B\ [O,x]_A&[O,2x]_B&&[I,x]_A&[I,-2x]_B&\ [O,x]_A&[O,2x]_B&[O,2x+1]_B&[I,x]_A&[I,-2x]_B&[I,-2x+2]_B\ [O,x]_A&[O,2x]_B&[O,2x-1]_B&[I,x]_A&[I,-2x]_B&[I,-2x-2]_B\ [O,x]_A&[I,x]_B&&[I,x]_A&[O,-x]_B&\ [O,x]_A&[I,x]_B&[I,x+2]_B&[I,x]_A&[O,-x]_B&[O,-x+1]_B\ [O,x]_A&[I,x]_B&[I,x-2]_B&[I,x]_A&[O,-x]_B&[O,-x-1]_B\ [O,x]_A&[O,x-1]_A&[O,2x-2]_B&[I,x]_A&[I,x-2]_A&[I,-2x-1]_B\ [O,x]_A&[O,x-1]_A&[I,x-1]_B&[I,x]_A&[I,x-2]_A&[O,-x+2]_B
end{array}$$
That's all ten possibilities in $B$ accounted for, from a start at either an outer vertex or an inner vertex in $A$. We have explicitly constructed paths of length at most $2$ between any two points.
Many pairs of points, of course, have other paths between them. For example, we can go from $[O,0]$ in $A$ to $[0]$ in $C$ and then to $[O,0]$ in $B$, instead of taking the direct edge. These extra paths don't always play nicely with the mod 5 structure we're using, so it's not obvious at a glance how many triangles and quadrilaterals there are. Still, extra paths aren't actually a problem; all we needed here was at least one.
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
$endgroup$
add a comment |
$begingroup$
I know I've seen something like this before - an old Vietnamese olympiad problem, maybe? Then again, I don't recall the exact statement, so that doesn't actually help me.
We just kind of have to get down and grubby with this one. With so much space to give - twelve redundant paths per vertex - there isn't any great symmetry to work with. Anyway, here's an explicit construction:
Group our $25$ vertices into three subsets $A,B,C$, of size $10,$ $10,$ and $5$. Those sets will have internal graphs that are two Petersen graphs (3-regular) and a pentagon (2-regular). Then, each vertex in $A$ will have edges to two vertices in $B$ and one in $C$ (total degree $3+2+1=6$), each vertex in $B$ will have edges to two vertices in $A$ and one in $C$ (total degree $3+2+1=6$), and each vertex in $C$ will have edges to two vertices in $A$ and two in $B$ (total degree $2+2+2=6$).
Label the vertices of $A$ and $B$ with pairs $[a,x]$ as shown:
Each $[O,x]$ has edges to $[O,x+1]$, $[O,x+2]$, and $[I,x]$. Each $[I,x]$ has edges to $[I,x+2]$, $[I,x-2]$, and $[O,x]$. The indices $x$ are, of course, interpreted mod $5$.
Label the vertices of the pentagon $C$ with a single index $[x]$, interpreted mod $5$. The internal edges of $C$ will go from $[x]$ to $[x+1]$ and $[x-1]$.
As is well-known, the pentagon and the Petersen graph each have diameter $2$. With just these edges, we have paths of length at most $2$ whenever our endpoints are in the same subset.
Now, we bring in the edges that cross boundaries. From $A$ to $C$, connect $[O,x]$ to $[2x]$ and $[I,x]$ to $[x]$. Starting at $[O,x]$, we can reach $[2x]$ in one step, then $[2x+1]$ and $[2x-1]$ in another step using the internal edges of $C$. Alternately, we can move to $[O,x+1]$ and then cross to $[2x+2]$ or move to $[O,x-1]$ and then cross to $[2x-2]$. That's all five vertices of $C$ reachable in two steps from an outer vertex of $A$.
From an inner vertex $[I,x]$ of $A$, we can cross to $[x]$ then step to $[x+1]$ or $[x-1]$, step to $[I,x+2]$ and cross to $[x+2]$, or step to $[I,x-2]$ and cross to $[x-2]$. Again, that's all five vertices of $C$ accounted for. Combine the two, and we can go from anywhere in $A$ to anywhere in $C$ in at most two steps. Of course, going from $C$ to $A$ just requires us to use the same path in reverse.
Between $B$ and $C$, add edges with the exact same indices that we had between $A$ and $C$. By the same proof, we then have paths of length at most $2$ between any point in $B$ and any point in $C$.
That just leaves paths between $A$ and $B$, the most complicated case. We add crossing edges as follows: from $[O,x]_A$ to $[O,2x]_B$, from $[O,x]_A$ to $[I,x]_B$, from $[I,x]_A$ to $[I,-2x]_B$, and from $[I,x]_A$ to $[O,-x]_B$.
A chart for the paths:
$$begin{array}{ccc|ccc}text{Start}&text{Step 1}&text{Step 2}&text{Start}&text{Step 1}&text{Step 2}\
hline [O,x]_A&[O,x+1]_A&[O,2x+2]_B&[I,x]_A&[I,x+2]_A&[I,-2x+1]_B\ [O,x]_A&[O,x+1]_A&[I,x+1]_B&[I,x]_A&[I,x+2]_A&[O,-x-2]_B\ [O,x]_A&[O,2x]_B&&[I,x]_A&[I,-2x]_B&\ [O,x]_A&[O,2x]_B&[O,2x+1]_B&[I,x]_A&[I,-2x]_B&[I,-2x+2]_B\ [O,x]_A&[O,2x]_B&[O,2x-1]_B&[I,x]_A&[I,-2x]_B&[I,-2x-2]_B\ [O,x]_A&[I,x]_B&&[I,x]_A&[O,-x]_B&\ [O,x]_A&[I,x]_B&[I,x+2]_B&[I,x]_A&[O,-x]_B&[O,-x+1]_B\ [O,x]_A&[I,x]_B&[I,x-2]_B&[I,x]_A&[O,-x]_B&[O,-x-1]_B\ [O,x]_A&[O,x-1]_A&[O,2x-2]_B&[I,x]_A&[I,x-2]_A&[I,-2x-1]_B\ [O,x]_A&[O,x-1]_A&[I,x-1]_B&[I,x]_A&[I,x-2]_A&[O,-x+2]_B
end{array}$$
That's all ten possibilities in $B$ accounted for, from a start at either an outer vertex or an inner vertex in $A$. We have explicitly constructed paths of length at most $2$ between any two points.
Many pairs of points, of course, have other paths between them. For example, we can go from $[O,0]$ in $A$ to $[0]$ in $C$ and then to $[O,0]$ in $B$, instead of taking the direct edge. These extra paths don't always play nicely with the mod 5 structure we're using, so it's not obvious at a glance how many triangles and quadrilaterals there are. Still, extra paths aren't actually a problem; all we needed here was at least one.
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
$endgroup$
I know I've seen something like this before - an old Vietnamese olympiad problem, maybe? Then again, I don't recall the exact statement, so that doesn't actually help me.
We just kind of have to get down and grubby with this one. With so much space to give - twelve redundant paths per vertex - there isn't any great symmetry to work with. Anyway, here's an explicit construction:
Group our $25$ vertices into three subsets $A,B,C$, of size $10,$ $10,$ and $5$. Those sets will have internal graphs that are two Petersen graphs (3-regular) and a pentagon (2-regular). Then, each vertex in $A$ will have edges to two vertices in $B$ and one in $C$ (total degree $3+2+1=6$), each vertex in $B$ will have edges to two vertices in $A$ and one in $C$ (total degree $3+2+1=6$), and each vertex in $C$ will have edges to two vertices in $A$ and two in $B$ (total degree $2+2+2=6$).
Label the vertices of $A$ and $B$ with pairs $[a,x]$ as shown:
Each $[O,x]$ has edges to $[O,x+1]$, $[O,x+2]$, and $[I,x]$. Each $[I,x]$ has edges to $[I,x+2]$, $[I,x-2]$, and $[O,x]$. The indices $x$ are, of course, interpreted mod $5$.
Label the vertices of the pentagon $C$ with a single index $[x]$, interpreted mod $5$. The internal edges of $C$ will go from $[x]$ to $[x+1]$ and $[x-1]$.
As is well-known, the pentagon and the Petersen graph each have diameter $2$. With just these edges, we have paths of length at most $2$ whenever our endpoints are in the same subset.
Now, we bring in the edges that cross boundaries. From $A$ to $C$, connect $[O,x]$ to $[2x]$ and $[I,x]$ to $[x]$. Starting at $[O,x]$, we can reach $[2x]$ in one step, then $[2x+1]$ and $[2x-1]$ in another step using the internal edges of $C$. Alternately, we can move to $[O,x+1]$ and then cross to $[2x+2]$ or move to $[O,x-1]$ and then cross to $[2x-2]$. That's all five vertices of $C$ reachable in two steps from an outer vertex of $A$.
From an inner vertex $[I,x]$ of $A$, we can cross to $[x]$ then step to $[x+1]$ or $[x-1]$, step to $[I,x+2]$ and cross to $[x+2]$, or step to $[I,x-2]$ and cross to $[x-2]$. Again, that's all five vertices of $C$ accounted for. Combine the two, and we can go from anywhere in $A$ to anywhere in $C$ in at most two steps. Of course, going from $C$ to $A$ just requires us to use the same path in reverse.
Between $B$ and $C$, add edges with the exact same indices that we had between $A$ and $C$. By the same proof, we then have paths of length at most $2$ between any point in $B$ and any point in $C$.
That just leaves paths between $A$ and $B$, the most complicated case. We add crossing edges as follows: from $[O,x]_A$ to $[O,2x]_B$, from $[O,x]_A$ to $[I,x]_B$, from $[I,x]_A$ to $[I,-2x]_B$, and from $[I,x]_A$ to $[O,-x]_B$.
A chart for the paths:
$$begin{array}{ccc|ccc}text{Start}&text{Step 1}&text{Step 2}&text{Start}&text{Step 1}&text{Step 2}\
hline [O,x]_A&[O,x+1]_A&[O,2x+2]_B&[I,x]_A&[I,x+2]_A&[I,-2x+1]_B\ [O,x]_A&[O,x+1]_A&[I,x+1]_B&[I,x]_A&[I,x+2]_A&[O,-x-2]_B\ [O,x]_A&[O,2x]_B&&[I,x]_A&[I,-2x]_B&\ [O,x]_A&[O,2x]_B&[O,2x+1]_B&[I,x]_A&[I,-2x]_B&[I,-2x+2]_B\ [O,x]_A&[O,2x]_B&[O,2x-1]_B&[I,x]_A&[I,-2x]_B&[I,-2x-2]_B\ [O,x]_A&[I,x]_B&&[I,x]_A&[O,-x]_B&\ [O,x]_A&[I,x]_B&[I,x+2]_B&[I,x]_A&[O,-x]_B&[O,-x+1]_B\ [O,x]_A&[I,x]_B&[I,x-2]_B&[I,x]_A&[O,-x]_B&[O,-x-1]_B\ [O,x]_A&[O,x-1]_A&[O,2x-2]_B&[I,x]_A&[I,x-2]_A&[I,-2x-1]_B\ [O,x]_A&[O,x-1]_A&[I,x-1]_B&[I,x]_A&[I,x-2]_A&[O,-x+2]_B
end{array}$$
That's all ten possibilities in $B$ accounted for, from a start at either an outer vertex or an inner vertex in $A$. We have explicitly constructed paths of length at most $2$ between any two points.
Many pairs of points, of course, have other paths between them. For example, we can go from $[O,0]$ in $A$ to $[0]$ in $C$ and then to $[O,0]$ in $B$, instead of taking the direct edge. These extra paths don't always play nicely with the mod 5 structure we're using, so it's not obvious at a glance how many triangles and quadrilaterals there are. Still, extra paths aren't actually a problem; all we needed here was at least one.
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
edited Feb 4 at 0:32
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
answered Feb 3 at 22:37
jmerryjmerry
17.1k11633
17.1k11633
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f2665019%2f6-regular-graph-of-order-25-and-diameter-2%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
