Skip to main content
broken image fixed (click 'rendered output' or 'side-by-side' to see the difference; image retrieved via Wayback Machine); for more info, see https://meta.mathoverflow.net/a/4058/70594
Source Link

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

  

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

 

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

 

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]
replaced http://s8.postimg.org/ with https://s8.postimg.org/
Source Link

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

http://s8.postimg.org/h1httar05/graphmo.png

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

http://s8.postimg.org/h1httar05/graphmo.png

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

http://s8.postimg.org/h1httar05/graphmo.png

Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get $4$ regular graph with $3,3'$ having all their neighbourhood in the two copies.

The edges:

[(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]