Skip to main content
Post Undeleted by benblumsmith
Corrected typo, added a framing phrase to final proof.
Source Link
benblumsmith
  • 2.9k
  • 18
  • 26

If I understand the question correctly and $H$ is finite, the answer is yesno.

(I first thought Let $H$ be the answer is no5-vertex graph consisting of a triangle with "tails" on two vertices; more explicitly let $V(H)=\{1,2,3,4,5\}$ and started to give counterexamples; then realized all my counterexamples failed for the same reason$E(H)=\{\{1,2\},\{2,3\},\{1,3\},\{1,4\},\{2,5\}\}$.)

LetThen $H$ be a graph withhas the stated property: for each edge $e$, there is a pairpart of vertices $u,v$ and a path from $u$ to $v$ containing $e$ and of length $\leq 2$ that is the unique path of length $\leq 2$ (up to orientation, I assume) between $u,v$. (Let us shorthand this by writing $P(e)$ for the assertion that for edge $e$ there exists such a path and "$H$ has property $P$" means $P(e)$ is satisfied for every $e\in E(H)$between its endpoints.) Explicitly:

I assert that if $H$ has diameterFor $> 2$$\{1,2\}$, then an edge can be added that preserves propertytake $P$ and the diameter of the new graph is$4\to 1\to 2$ or $>1$$1\to 2\to 5$. Since adding an edge cannot increase the diameter and can only be done a finite number of times before the diameter becomes

For $1$$\{2,3\}$, this shows inductively that one will arrive at the desired graph $G$ of diameter $2$ and having propertytake $P$$5\to 2\to 3$.

If $H$ has diameterFor $>2$$\{1,3\}$, then there is a pair of vertices $u,v$ with no path of length $\leq 2$ between them. Add the edgetake $(u,v)$$4\to 1\to 3$.

I claim that the new graph $H'$ has the desired property $P$. First, the pathFor $(u,v)$ is the unique path of length$\{1,4\}$ and $\leq 2$ between$\{2,5\}$ take $u$$1\to 4$ and $v$, so the new edge has the desired property$2\to 5$ respectively. Secondly

However, all other edges $e'\in E(H')\setminus (u,v) = E(H)$ satisfy $P(e')$ in $H'$. To see this: as $e'$$H$ is an edge ofnot the originalsubgraph of any minimal graph of diameter $H$$2$ on five vertices. In fact, $P(e')$ is true in $H$no such graph contains a triangle. Proof, so there isby fully classifying minimal diameter 2 graphs on 5 vert's: if a pairminimal graph of diameter 2 on five vertices in $V(H)$ withcontains a path containing $e'$vertex of length $\leq 2$ that is the unique such path between them in $H$. If there is another such path indegree 4, it contains the augmented graphstar $H'$,$K_{1,4}$ and then it must go through $(u,v)$equals this since this is min. Then the two paths together give a cyclediameter 2. If it contains no vertex of lengthdegree $\leq 2+2=4$$>2$, containing $(u,v)$. Bythen it is clearly the assumption that $u,v$ are not linked by a path of length $\leq 2$ in$5$-cycle $H$,$C_5$ since again it must be thatcontain this cyclegraph (callotherwise it would have diameter $C$$>2$) has length exactly 4 and $u,v$ were linked bythis too is min. diameter 2. Finally, if it contains a pathvertex of lengthdegree $3$ in the original graphbut none of degree $H$$4$, and $e'$ is one of the three edges of this path. But then the path consisting of $e'$ itself witnessesit must be $P(e')$: if$K_{2,3}$ since, say the vertices of $e'$ aredegree 3 vertex is $x$$a$ and $y$it's adjacent to (one of them could be$b,c,d$. If the final vertex $=u$ or$e$ is connected to only $v$, or not)$b$, then a path linking $x$ and $y$ but avoiding$b$ is forced to be degree $e$ has length at least$4$ to achieve diameter $3$:$2$, contradiction; if it lies entirely init's connected only to $H$ this is true by the assumption about$b$ and $H$$c$, while if it goes throughthen to achieve diameter 2 one of them must be connected to $(u,v)$$d$ and then it plusthe graph contains the $e'$ give a cycle containing$5$-cycle properly and is not minimal. Thus $(u,v)$ which$e$ must be length at leastadjacent to $4$.

Finally$b,c,d$, $H'$ still has diameterso the graph contains $>1$ because$K_{2,3}$, and then it equals this since it is not a complete graph (since a complete graph does not have property $P$)already min. This completes the argumentdiameter 2.

If I understand the question correctly and $H$ is finite, the answer is yes.

(I first thought the answer is no and started to give counterexamples; then realized all my counterexamples failed for the same reason.)

Let $H$ be a graph with the stated property: for each edge $e$, there is a pair of vertices $u,v$ and a path from $u$ to $v$ containing $e$ and of length $\leq 2$ that is the unique path of length $\leq 2$ (up to orientation, I assume) between $u,v$. (Let us shorthand this by writing $P(e)$ for the assertion that for edge $e$ there exists such a path and "$H$ has property $P$" means $P(e)$ is satisfied for every $e\in E(H)$.)

I assert that if $H$ has diameter $> 2$, then an edge can be added that preserves property $P$ and the diameter of the new graph is $>1$. Since adding an edge cannot increase the diameter and can only be done a finite number of times before the diameter becomes $1$, this shows inductively that one will arrive at the desired graph $G$ of diameter $2$ and having property $P$.

If $H$ has diameter $>2$, then there is a pair of vertices $u,v$ with no path of length $\leq 2$ between them. Add the edge $(u,v)$.

I claim that the new graph $H'$ has the desired property $P$. First, the path $(u,v)$ is the unique path of length $\leq 2$ between $u$ and $v$, so the new edge has the desired property. Secondly, all other edges $e'\in E(H')\setminus (u,v) = E(H)$ satisfy $P(e')$ in $H'$. To see this: as $e'$ is an edge of the original graph $H$, $P(e')$ is true in $H$, so there is a pair of vertices in $V(H)$ with a path containing $e'$ of length $\leq 2$ that is the unique such path between them in $H$. If there is another such path in the augmented graph $H'$, then it must go through $(u,v)$. Then the two paths together give a cycle of length $\leq 2+2=4$, containing $(u,v)$. By the assumption that $u,v$ are not linked by a path of length $\leq 2$ in $H$, it must be that this cycle (call it $C$) has length exactly 4 and $u,v$ were linked by a path of length $3$ in the original graph $H$, and $e'$ is one of the three edges of this path. But then the path consisting of $e'$ itself witnesses $P(e')$: if the vertices of $e'$ are $x$ and $y$ (one of them could be $=u$ or $v$, or not), then a path linking $x$ and $y$ but avoiding $e$ has length at least $3$: if it lies entirely in $H$ this is true by the assumption about $H$, while if it goes through $(u,v)$ then it plus $e'$ give a cycle containing $(u,v)$ which must be length at least $4$.

Finally, $H'$ still has diameter $>1$ because it is not a complete graph (since a complete graph does not have property $P$). This completes the argument.

If I understand the question correctly, the answer is no.

Let $H$ be the 5-vertex graph consisting of a triangle with "tails" on two vertices; more explicitly let $V(H)=\{1,2,3,4,5\}$ and $E(H)=\{\{1,2\},\{2,3\},\{1,3\},\{1,4\},\{2,5\}\}$.

Then $H$ has the stated property: each edge is part of a path of length $\leq 2$ that is the unique such path between its endpoints. Explicitly:

For $\{1,2\}$, take $4\to 1\to 2$ or $1\to 2\to 5$.

For $\{2,3\}$, take $5\to 2\to 3$.

For $\{1,3\}$, take $4\to 1\to 3$.

For $\{1,4\}$ and $\{2,5\}$ take $1\to 4$ and $2\to 5$ respectively.

However, $H$ is not the subgraph of any minimal graph of diameter $2$ on five vertices. In fact, no such graph contains a triangle. Proof, by fully classifying minimal diameter 2 graphs on 5 vert's: if a minimal graph of diameter 2 on five vertices contains a vertex of degree 4, it contains the star $K_{1,4}$ and then it equals this since this is min. diameter 2. If it contains no vertex of degree $>2$, then it is clearly the $5$-cycle $C_5$ since again it must contain this graph (otherwise it would have diameter $>2$) and this too is min. diameter 2. Finally, if it contains a vertex of degree $3$ but none of degree $4$, then it must be $K_{2,3}$ since, say the degree 3 vertex is $a$ and it's adjacent to $b,c,d$. If the final vertex $e$ is connected to only $b$, then $b$ is forced to be degree $4$ to achieve diameter $2$, contradiction; if it's connected only to $b$ and $c$, then to achieve diameter 2 one of them must be connected to $d$ and then the graph contains the $5$-cycle properly and is not minimal. Thus $e$ must be adjacent to $b,c,d$, so the graph contains $K_{2,3}$, and then it equals this since it is already min. diameter 2.

Post Deleted by benblumsmith
Post Undeleted by benblumsmith
Previous answer was incorrect.
Source Link
benblumsmith
  • 2.9k
  • 18
  • 26

If I understand the question correctly and $H$ is finite, the answer is yes.

(I first thought the answer is no and started to give counterexamples; then realized all my counterexamples failed for the same reason.)

Let $H$ be a star-shaped graph. with the stated property: for each edge (I.e.$e$, there is a vertexpair of vertices $v_0$$u,v$ and a path from $n$ vertices$u$ to $v_1,\dots,v_n$$v$ containing $e$ and of length $\leq 2$ that is the unique path of length $\leq 2$ (up to orientation, withI assume) between $u,v$. (Let us shorthand this by writing $P(e)$ for the assertion that for edge set $(v_0,v_i)$$e$ there exists such a path and "$H$ has property $P$" means $P(e)$ is satisfied for every $1\leq i\leq n$$e\in E(H)$.) Because

I assert that if $H$ is a treehas diameter $> 2$, every paththen an edge can be added that preserves property $P$ and the diameter of the new graph is unique, so $H$ has$>1$. Since adding an edge cannot increase the diameter and can only be done a finite number of times before the diameter becomes $1$, this shows inductively that one will arrive at the desired graph $G$ of diameter $2$ and having property $P$.

If (For any edge$H$ has diameter $(v_0,v_i)$$>2$, take thethen there is a pair of vertices $u,v$ with no path consisting of only thatlength $\leq 2$ between them. Add the edge $(u,v)$.)

However, it's not possible to add an edge and preserveI claim that the property. Any new edgegraph $(v_i,v_j)$ will force a triangle$H'$ has the desired property $P$. First, the path $(u,v)$ is the unique path of length $\leq 2$ between $u$ and $v$, so the new edge will not havehas the desired property. Secondly, all other edges $e'\in E(H')\setminus (u,v) = E(H)$ satisfy $P(e')$ in $H'$. To see this: any path of length 2 containing it gets from oneas $e'$ is an edge of its vertices tothe original graph $v_0$$H$, (or vice versa)$P(e')$ is true in $H$, butso there is a pair of vertices in $V(H)$ with a path containing $e'$ of length $1$ not containing it$\leq 2$ that doesis the sameunique such path between them in $H$. SimilarlyIf there is another such path in the augmented graph $H'$, then it must go through $(u,v)$. Then the pathtwo paths together give a cycle of length $(v_i,v_j)$$\leq 2+2=4$, containing $(u,v)$. By the assumption that $u,v$ are not linked by a path of length $1$ can$\leq 2$ in $H$, it must be replacedthat this cycle (call it $C$) has length exactly 4 and $u,v$ were linked by thea path of length $(v_i,v_0),(v_0,v_j)$ to avoid this edge.

Furthermore$3$ in the original graph $H$, adding subsequent edges will not solveand $e'$ is one of the problemthree edges of this path. AnyBut then the path consisting of length $2$ containing$e'$ itself witnesses $(v_i,v_j)$$P(e')$: if the vertices of $e'$ are $x$ and $y$ (wlog, sayone of them could be $(v_i,v_j),(v_j,v_k)$$=u$ or $v$, or not) can be replaced, then a path linking $x$ and $y$ but avoiding $e$ has length at least $3$: if it lies entirely in $H$ this is true by the assumption about $(v_i,v_0),(v_0,v_k)$$H$, while if it goes through $(u,v)$ then it plus $e'$ give a cycle containing $(u,v)$ which must be length at least $4$.

Finally, $H'$ still has diameter $>1$ because it is not a complete graph (since a complete graph does not have property $P$). This completes the argument.

If I understand the question correctly, the answer is no.

Let $H$ be a star-shaped graph. (I.e. a vertex $v_0$ and $n$ vertices $v_1,\dots,v_n$, with edge set $(v_0,v_i)$ for $1\leq i\leq n$.) Because $H$ is a tree, every path is unique, so $H$ has the desired property. (For any edge $(v_0,v_i)$, take the path consisting of only that edge.)

However, it's not possible to add an edge and preserve the property. Any new edge $(v_i,v_j)$ will force a triangle, and the new edge will not have the desired property: any path of length 2 containing it gets from one of its vertices to $v_0$ (or vice versa), but there is a path of length $1$ not containing it that does the same. Similarly, the path $(v_i,v_j)$ of length $1$ can be replaced by the path $(v_i,v_0),(v_0,v_j)$ to avoid this edge.

Furthermore, adding subsequent edges will not solve the problem. Any path of length $2$ containing $(v_i,v_j)$ (wlog, say $(v_i,v_j),(v_j,v_k)$) can be replaced by $(v_i,v_0),(v_0,v_k)$).

If I understand the question correctly and $H$ is finite, the answer is yes.

(I first thought the answer is no and started to give counterexamples; then realized all my counterexamples failed for the same reason.)

Let $H$ be a graph with the stated property: for each edge $e$, there is a pair of vertices $u,v$ and a path from $u$ to $v$ containing $e$ and of length $\leq 2$ that is the unique path of length $\leq 2$ (up to orientation, I assume) between $u,v$. (Let us shorthand this by writing $P(e)$ for the assertion that for edge $e$ there exists such a path and "$H$ has property $P$" means $P(e)$ is satisfied for every $e\in E(H)$.)

I assert that if $H$ has diameter $> 2$, then an edge can be added that preserves property $P$ and the diameter of the new graph is $>1$. Since adding an edge cannot increase the diameter and can only be done a finite number of times before the diameter becomes $1$, this shows inductively that one will arrive at the desired graph $G$ of diameter $2$ and having property $P$.

If $H$ has diameter $>2$, then there is a pair of vertices $u,v$ with no path of length $\leq 2$ between them. Add the edge $(u,v)$.

I claim that the new graph $H'$ has the desired property $P$. First, the path $(u,v)$ is the unique path of length $\leq 2$ between $u$ and $v$, so the new edge has the desired property. Secondly, all other edges $e'\in E(H')\setminus (u,v) = E(H)$ satisfy $P(e')$ in $H'$. To see this: as $e'$ is an edge of the original graph $H$, $P(e')$ is true in $H$, so there is a pair of vertices in $V(H)$ with a path containing $e'$ of length $\leq 2$ that is the unique such path between them in $H$. If there is another such path in the augmented graph $H'$, then it must go through $(u,v)$. Then the two paths together give a cycle of length $\leq 2+2=4$, containing $(u,v)$. By the assumption that $u,v$ are not linked by a path of length $\leq 2$ in $H$, it must be that this cycle (call it $C$) has length exactly 4 and $u,v$ were linked by a path of length $3$ in the original graph $H$, and $e'$ is one of the three edges of this path. But then the path consisting of $e'$ itself witnesses $P(e')$: if the vertices of $e'$ are $x$ and $y$ (one of them could be $=u$ or $v$, or not), then a path linking $x$ and $y$ but avoiding $e$ has length at least $3$: if it lies entirely in $H$ this is true by the assumption about $H$, while if it goes through $(u,v)$ then it plus $e'$ give a cycle containing $(u,v)$ which must be length at least $4$.

Finally, $H'$ still has diameter $>1$ because it is not a complete graph (since a complete graph does not have property $P$). This completes the argument.

Post Deleted by benblumsmith
Source Link
benblumsmith
  • 2.9k
  • 18
  • 26

If I understand the question correctly, the answer is no.

Let $H$ be a star-shaped graph. (I.e. a vertex $v_0$ and $n$ vertices $v_1,\dots,v_n$, with edge set $(v_0,v_i)$ for $1\leq i\leq n$.) Because $H$ is a tree, every path is unique, so $H$ has the desired property. (For any edge $(v_0,v_i)$, take the path consisting of only that edge.)

However, it's not possible to add an edge and preserve the property. Any new edge $(v_i,v_j)$ will force a triangle, and the new edge will not have the desired property: any path of length 2 containing it gets from one of its vertices to $v_0$ (or vice versa), but there is a path of length $1$ not containing it that does the same. Similarly, the path $(v_i,v_j)$ of length $1$ can be replaced by the path $(v_i,v_0),(v_0,v_j)$ to avoid this edge.

Furthermore, adding subsequent edges will not solve the problem. Any path of length $2$ containing $(v_i,v_j)$ (wlog, say $(v_i,v_j),(v_j,v_k)$) can be replaced by $(v_i,v_0),(v_0,v_k)$).