graph theory help (1 Viewer)

[seanieg89]

changed what i said and now it makes sense i think
kept the proof for k(m,n) max when |m-n| = minimised

"the maximum number of edges in a simple graph on 2n vertices can be found by splitting the vertices in to 2 independent sets, A and B where the number of nodes in A (a) = the number of nodes in B (b)

A condition of bipartness is that the graph contains no odd numbered cycles, satisfying our ogirinal conditons

*proof for K(m,n) thing*

If the vertex set contains 2n+1 nodes, the maximum number of edges is achieved by forming a bipartite graph, Km,n where |m-n| = 1

still has some loose ends/could be phrased better but i think that's ~less~ flawed

Depends on the wording of the question. What your have shown is that:

"The most edges a bipartite graph on n vertices can have without containing triangles is blah."

where the "without containing triangles" part is redundant because of the "bipartite". Depending on what the question is asking you for, it would be ideal to remove the word "bipartite" from that sentence.

 

[kfnmpah]

yep you are right it doesn't *have * to be bipartite because it could have a cycle of some 2n-1 where n =/=2 (because q says no triangles not just no odd cycles)