Tuesday, 8 February 2011

Graphs where every two vertices have odd number of mutual neighbours

Maybe I'm missing something, but I'm not sure that the third condition actually generates what I'll call odd graphs. For example, if I let $A$ be the graph consisting of a single vertex and $B$ be the graph consisting of two isolated vertices, then clearly both $A$ and $B$ are even. However, if I form the $A-B-C$ construction with this choice of $A$ and $B$ I get a graph with an even number of vertices, which can't be odd by the proof of the cute question.



We can fix this by further insisting that each vertex of $A$ and $C$ have odd degree. I'll call such graphs oddly even. Note that a disjoint union of two oddly even graphs is still oddly even, so it really isn't necessary to have a $A-B-C$ construction, we only need a $A-B$ construction. Furthermore, it is not necessary that $B$ is an odd clique; $B$ can in fact be any odd graph.



We thus have the following theorem.



Theorem. Let $A$ be an oddly even graph and $B$ be an odd graph. Then the graph $A-B$ formed by taking $A$ and $B$ and adding all edges between $A$ and $B$ is odd.



So, I guess the answer to the question is no.

No comments:

Post a Comment