Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

After working for sometime I figured out the following course of action. (from a few sample cases on 4 and 5 vertices)

i) I wanted to prove that the graph had no odd degree vertex.

ii) There exists at leat one vertex adjacent to all other vertices.

If I can do these, then if n = |G|, (n-1) is even- hence, n is odd.

My friend told me that by considering a typical vertex and its neighbours and considering the subgraph induced on it, he has been able to prove the 1st part.

So now to prove the 2nd part, I was cosidering a vertex with maximum degree and if it does not have the above property I wanted to derive a contradiction.

But I think I am stuck.

Any suggestions?

share|improve this question

5 Answers 5

You've already shown that every vertex $v$ has even degree, for if it had odd degree, than look at its set of neighbors with the induced subgraph structure, $H$. H$$ has an odd number of vertices with every vertex having odd degree, which is a contradiction.

Now, consider the adjacency matrix $A$ of $G,$ where we consider a vertex to be adjacent to itself. Then the condition of $|N(u)\cap N(v)|$ being odd translates to $A^2=F,$ where $F$ is the matrix with each entry being 1. Since every vertex of $A$ has even degree, we have the identity $AF=F$. Therefore $F^2=FA^2=F$. The identity $F^2=F$ exactly means that the number of vertices is odd. This completes the proof.

share|improve this answer
1  
Very nice, but you should have added that the adjacency matrix that you construct is over F_2 rather than over Q. –  darij grinberg Mar 6 '10 at 17:53
    
right you are. my bad :) –  jacob Mar 6 '10 at 23:21
    
Good answer. I'd replace $FA^2$ by $A^2 F$ to make it slightly clearer. –  Tony Huynh Mar 8 '10 at 19:33

Jacob seems to have beaten me to it by a few minutes, but an algebraic graph theory proof works nicely, so I'll add my slight variant.

If $A$ is the $n \times n$ adjacency matrix of the graph, which we assume has no odd degree vertices, then over $Z_2$ the condition shows that $A^2$ has 0s on the diagonal and 1s elsewhere - i.e. that $A^2 = J - I$.

But (again over $Z_2$) $J-I$ has rank $n$ if $n$ is even. But $A$ does not have full rank as $A j = 0$ where $j$ is the all-ones vector (because graph has no odd degree vertices), and so neither can $A^2$.

share|improve this answer

It's not true, though, is it? The graph with no vertices satisfies your property vacuously and has an even number of vertices.

share|improve this answer
1  
+1, since such trivial cases may lead into trouble when taken too lightly. –  darij grinberg Mar 6 '10 at 17:54
    
@darij grinberg : Yet you must show that that this is not significant : Is the empty graph an initial object in the category of graphs ? In which respect does and empty set have an even number of elements ? –  Jérôme JEAN-CHARLES Nov 21 '11 at 14:36

I showed this on http://www.mathlinks.ro/viewtopic.php?t=68109 . Very nice problem.

share|improve this answer

I proved over here that statement ii) holds when we make the stronger assumption that $|N(u) \cap N(v)|$ is exactly $1$ for every $u, v$.

Most of the argument probably does not generalize, but at least one piece of it does. That part is that if $G$ is a minimal counterexample, then the complement graph is connected. I'll prove this by contradiction:

Let $X$ and $Y$ be a partition of the vertices into two nonempty parts such that every vertex in X is connected to every vertex in Y. If $X$ has even size, then we see that $Y$ has the same property $G$ has and is smaller than $G$, so $Y$ has odd size and $G$ has an odd number of vertices. If $X$ has odd size, then if we collapse $X$ to a point $x$ we still have the property that $|N(u) \cap N(v)|$ is odd for $u, v$ in $Y$, and also for any $u$ in $Y$, $|N(x)\cap N(u)|$ is odd by your step i), so $Y\cup x$ satisfies the same properties $G$ does and contains a vertex that is connected to everything, so $Y\cup x$ has odd size, so $G$ has odd size.

Unfortunately, I can't see any obvious nice relationship that must be satisfied by two nonadjacent vertices in our graph $G$...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.