Re: Tough little graph theory question

On Nov 28, 8:35 pm, flamegrilledmon...@xxxxxxxxx wrote:

Let G be a graph. Any two vertices joined by an edge have no common
neighbours and any two vertices not joined by an edge have exactly one
common neighbour. Assuming there is no vertex joined to all others
this implies that G is a regular graph?

Is this true?

Yes.

If so, is this a well known problem with solution?

Probably. It sounds like a homework problem. So as not to spoil your
fun, I'll just give hints.

1. Show that any two *nonadjacent* vertices of G must have equal
degrees.

2. Finish the proof of regularity by showing that the complement of G
is connected. (In fact, the complement has diameter 2, but that's more
than you need.)

.

Relevant Pages

  • Re: Tough little graph theory question
    ... Let G be a graph. ... Any two vertices joined by an edge have no common ... neighbours and any two vertices not joined by an edge have exactly one ... every pair of vertices has distance 1 or 2 from each other. ...
    (sci.math)
  • Re: Tough little graph theory question
    ... Let G be a graph. ... Any two vertices joined by an edge have no common ... neighbours and any two vertices not joined by an edge have exactly one ... 5-cycle, which of course, is regular. ...
    (sci.math)
  • Re: Using a directed graph as an undirected one in a shortest path algorithm
    ... Your problem statement makes perfect sense to me. ... of "n"th nearest neighbours of each vertex in the graph. ... The OCaml code is less than half the ...
    (comp.programming)
  • Re: How to split a one-pixel-width graph into line segments?
    ... problem is to split this graph into line segments under 8- ... I think of a very easy method: just count the neighbours of each pixel ... neighbour => extremity of a segment ...
    (sci.image.processing)
  • Re: What?
    ... What common history have Finland and Norway? ... We are three neighbours, isn't it enough? ... Estonia, Latvia, and Lithuania are three small countries whose ...
    (soc.culture.baltics)