Return to Answer

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question Existence of a nice subset of edges in $k-$regular simple graphs?. It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.

More generally, the situation can be resumed as follows:

Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.

Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$, we set $$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$

Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if $\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.

(This result follows easily from Kevin P. Costello answer to question Existence of a nice subset of edges in $k-$regular simple graphs? .)

Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$. This condition is not sufficient, one has to check the marriage-condition $\sharp(\mathcal A(S))\geq \sharp(S)$ for all subsets $S\subset V$, not only for vertices (regularity of the graph $G$ is however not necessary.)

Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$ of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching $f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$

The marriage-condition in the Theorem is for example satisfied if the number $\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of $v$. This is for instance the case if $G$ is a regular graph of diameter $2$.

Gerhard Paseman's examples of a regular graph violating the marriage-condition with $\mathcal A(v)$ never empty can be described as follows.

Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices $i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.

The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.

Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$ is reduced to the unique vertex $e_0$.

Correction: $ABCDef$ does not work for a stupid reason pointed out by Gerhard Paseman. Take $ABCdeFgh$ instead. Considering $S=\lbrace A_+,A_-\rbrace$, we have $\mathcal A(A_+,A_-)=e_0$ which violates the marriage condition.

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question Existence of a nice subset of edges in $k-$regular simple graphs?. It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.

More generally, the situation can be resumed as follows:

Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.

Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$, we set $$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$

Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if $\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.

(This result follows easily from Kevin P. Costello answer to question Existence of a nice subset of edges in $k-$regular simple graphs? .)

Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$. This condition is not sufficient, one has to check the marriage-condition $\sharp(\mathcal A(S))\geq \sharp(S)$ for all subsets $S\subset V$, not only for vertices (regularity of the graph $G$ is however not necessary.)

Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$ of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching $f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$

The marriage-condition in the Theorem is for example satisfied if the number $\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of $v$. This is for instance the case if $G$ is a regular graph of diameter $2$.

Gerhard Paseman's examples of a regular graph violating the marriage-condition with $\mathcal A(v)$ never empty can be described as follows.

Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices $i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.

The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.

Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$ is reduced to the unique vertex $e_0$.

Correction: $ABCDef$ does not work for a stupid reason pointed out by Gerhard Paseman. Take $ABCdeFgh$ instead. Considering $S=\lbrace A_+,A_-\rbrace$, we have $\mathcal A(A_+,A_-)=e_0$ which violates the marriage condition.

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question Existence of a nice subset of edges in $k-$regular simple graphs?. It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.

More generally, the situation can be resumed as follows:

Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.

Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$, we set $$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$

Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if $\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.

(This result follows easily from Kevin P. Costello answer to question Existence of a nice subset of edges in $k-$regular simple graphs? .)

Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$. This condition is not sufficient, one has to check the marriage-condition $\sharp(\mathcal A(S))\geq \sharp(S)$ for all subsets $S\subset V$, not only for vertices (regularity of the graph $G$ is however not necessary.)

Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$ of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching $f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$

The marriage-condition in the Theorem is for example satisfied if the number $\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of $v$. This is for instance the case if $G$ is a regular graph of diameter $2$.

Gerhard Paseman's examples of a regular graph violating the marriage-condition with $\mathcal A(v)$ never empty can be described as follows.

Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices $i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.

The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.

Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$ is reduced to the unique vertex $e_0$.

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question Existence of a nice subset of edges in $k-$regular simple graphs?. It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.

More generally, the situation can be resumed as follows:

Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.

Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$, we set $$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$

Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if $\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.

(This result follows easily from Kevin P. Costello answer to question Existence of a nice subset of edges in $k-$regular simple graphs? .)

Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$. This condition is not sufficient, one has to check the marriage-condition $\sharp(\mathcal A(S))\geq \sharp(S)$ for all subsets $S\subset V$, not only for vertices (regularity of the graph $G$ is however not necessary.)

Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$ of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching $f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$

The marriage-condition in the Theorem is for example satisfied if the number $\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of $v$. This is for instance the case if $G$ is a regular graph of diameter $2$.

Gerhard Paseman's examples of a regular graph violating the marriage-condition with $\mathcal A(v)$ never empty can be described as follows.

Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices $i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.

The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.

Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$ is reduced to the unique vertex $e_0$.

Correction: $ABCDef$ does not work for a stupid reason pointed out by Gerhard Paseman. Take $ABCdeFgh$ instead. Considering $S=\lbrace A_+,A_-\rbrace$, we have $\mathcal A(A_+,A_-)=e_0$ which violates the marriage condition.

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question Existence of a nice subset of edges in $k-$regular simple graphs?. It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.

More generally, the situation can be resumed as follows:

Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.

Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$, we set $$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$

Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if $\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.

(This result follows easily from Kevin P. Costello answer to question Existence of a nice subset of edges in $k-$regular simple graphs? .)

Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$. This condition is not sufficient, one has to check the condition for all sets $\mathcal A(S)$ with $S\subset V$ (regularity of the graph $G$ is however not necessary.)

Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$ of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching $f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$

The marriage-condition in the Theorem is for example satisfied if the number $\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of $v$. This is for instance the case if $G$ is a regular graph of diameter $2$.

Gerhard Paseman's examples of a regular graph violating the marriage-condition with $\mathcal A(v)$ never empty can be described as follows.

Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices $i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.

The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.

Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$ is reduced to the unique vertex $e_0$.

Gerhard's example is sharp, the answer is "yes" for $D=2$. Indeed, consider the complementary graph and apply the answer to question Existence of a nice subset of edges in $k-$regular simple graphs?. It yields cycles of a fixpoint-free permutation sending vertices to non-adjacent vertices.

More generally, the situation can be resumed as follows:

Call a vertex permutation $\sigma$ of a finite graph $G=(V,E)$ an antipodal map if $d(v,\sigma(v))=D$ for all $v\in V$ where $D$ denotes the diameter of $G$.

Given a subset $S\subset V$ of vertices of a finite graph $G$ with diameter $D$, we set $$\mathcal A(S)=\lbrace v\in V\ \vert\ \exists w\in S, d(v,w)=D\rbrace\ .$$

Theorem: A finite graph $G=(V,E)$ has an antipodal map if and only if $\sharp(\mathcal A(S))\geq \sharp(S)$ for every subset $S\subset V$.

(This result follows easily from Kevin P. Costello answer to question Existence of a nice subset of edges in $k-$regular simple graphs? .)

Remark that Alain Valette required $\mathcal A(v)$ to be non-empty for every vertex $v$. This condition is not sufficient, one has to check the marriage-condition $\sharp(\mathcal A(S))\geq \sharp(S)$ for all subsets $S\subset V$, not only for vertices (regularity of the graph $G$ is however not necessary.)

Proof: Associate to every vertex $v$ of $G$ a pair $\lbrace f_v,m_v\rbrace$ of twins of opposite genders. A woman $f_v$ accepts a man $m_w$ as a husband if and only if $d(v,w)=D$. An antipodal map $\sigma$ yields thus a complete matching $f_v,m_{\sigma(v)}$ into married couples and we can apply Hall's (marriage-)Theorem.$\Box$

The marriage-condition in the Theorem is for example satisfied if the number $\sharp(\mathcal A(v))$ of vertices at distance $D$ to a given vertex is independent of $v$. This is for instance the case if $G$ is a regular graph of diameter $2$.

Gerhard Paseman's examples of a regular graph violating the marriage-condition with $\mathcal A(v)$ never empty can be described as follows.

Consider a necklace $N$ consisting of $a$ fat and of $b$ ordinary beads. Associate to $N$ a graph $G=G(N)$ with $2a+b$ vertices as follows: A fat bead $i$ gives rise to two vertices $i_+,i_-$ and an ordinary bead $j$ gives rise to a vertex $j_0$. Two distinct vertices $i_{\star},j_\star$ are adjacent if either $i=j$ of if $i$ and $j$ are adjacent beads.

The graph $G(N)$ is then $3-$regular if all maximal non-empty substrings of consecutive ordinary beads in $N$ contain exactly $2$ ordinary beads.

Denoting fat/ordinary beads by uppercase/lowercase letters, the graph associated to the necklace $ABCDef$ is $3-$regular and violates the marriage-condition by considering the set $S$ consisting of the two vertices $B_+,B_-$. Indeed, $\mathcal A(B_+,B_-)$ is reduced to the unique vertex $e_0$.