graph theory help (1 Viewer)

[kfnmpah]

"what is the maximum number of edges a graph with 6 vertices can have with no cycles of length 3"

i'm assuming there can be cycles of more than 3

i got 9


BUT i want to know what the pattern is if one exists. I know there is one for planar graphs (Kuratowski's theorem) but what if they aren't planar?
the formula (https://en.wikipedia.org/wiki/Planar_graph#Other_planarity_criteria) for planar graphs gives me max of 8 edges but i can get 9 edges with no closed cycles so that's not the right formula.

tl;dr is there a formula relating vertices with number of edges in a graph with no cycles of length 3?

 

[kfnmpah]

i also tried looking at graphs with more edges to find a pattern but i'm probably counting wrong and i'm not really getting anywhere

v: 4 5 6 7 8 9 10
e: 4 5 9 10 16 15 24

eh

 

[kfnmpah]

ok so this is annoying me a lot i fiddled around for a bit and if there are an even number of nodes i *think* the total number of edges without a loop of 3 is

(n-1) + (n-3) + (n-5) +...+(n-(n-1)) where n is the number of nodes and, again, n is even

now what i am ded

 

[kfnmpah]

example:

e.g. 8 nodes numbered from 1-8
4 are even 4 are odd
O1(1)--> E1(2), E2(4), E3(6) and E4(8)
E1(2)--> O2(3), O3(5), O4(7)
edges = (n/2) + (n/2)-1
= n-1
O2(3)--> E2(4), E3(6), E4(8)
E2(4)--> O3(5), O4(7)
edges = (n/2)-1 + (n/2)-2
= n-3
O3(5)--> E3(6), E4(8)
E3(6)--> O4(7)
edges = (n/2)-2 + (n/2)-3
= n-5
O4(7)--> E4(8)
E4(8)--> -
edges = (n/2)-3 + (n/2)-4
= n-7

total where n = 8 is

(8-1) + (8-3) + (8-5) + (8-7) = 8^(8/2) - (1+3+5+7)

using formula for adding n odd numbers:

total edges = (8).(4) - 4^2
= 16

general formula = (n).(n/2) - (n/2)^2


hahahah YESSSSSSSSSSSSS i am the best

 

[seanieg89]

is a tight upper bound which you can prove by induction.

Intuitively, the most efficient way of constructing such graphs is splitting your vertex set into two sets A and B of roughly equal size and then joining every vertex in A to every vertex in B.

 

[kfnmpah]

man i certainly beat the fuck around the bush didn't i

but i understand what i was doing so i guess that's not so bad

how can i prove that by splitting the set into 2 that i'm not going to get any cycles of 3. i mean intuitively yes it makes sense but how can i *prove* it
also man i haven't done induction in about a million year and i forget hehe
start with a simple case and prove it will always work for n+1 (or something) shit dude

 

[seanieg89]

man i certainly beat the fuck around the bush didn't i

but i understand what i was doing so i guess that's not so bad

how can i prove that by splitting the set into 2 that i'm not going to get any cycles of 3. i mean intuitively yes it makes sense but how can i *prove* it
also man i haven't done induction in about a million year and i forget hehe
start with a simple case and prove it will always work for n+1 (or something) shit dude

Depends how rigorous you want to be. You could say something like:

Suppose distinct vertices 1,2,3 form a triangle and without loss of generality assume 1 is in set A. Then by the way we defined our graph, 2 (being adjacent to 1) must be in set B. Similarly, 3 must be in set A. But now 1 and 3 are two adjacent vertices both in set A, contradiction.

Induction jumping by 2 each time is probably quicker here.

 

[kfnmpah]

i understand the point explanation but have literally 0 idea about how to priove it by induction. literally 0.

how to start, please?

 

[kfnmpah]

yeah so how do i prove this by induction with (n+2) i have no idea what to do

sub in n = (n+2) in (x/2)^2 and then what no i have (n^2 + 4n + 4)/4 and idk what to do with it

 

[kfnmpah]

it is also probably wrong

halp

 

[seanieg89]

Here is a proof for an even number of vertices, try to prove the odd case yourself (it is almost exactly the same).

Our claim is that the graph on 2n vertices can have at most n^2 edges without containing a triangle, we prove this inductively.

1. The claim is clear for n=1, we simply join the two vertices with the only edge possible.

2. Assume we have proven the result for some positive integer n. Now consider a graph G on 2n+2=2(n+1) vertices.

3. Let A be a subset of the vertex set of G, containing exactly 2n vertices. Let B be the remaining 2 vertices x and y. Without loss of generality we may choose A such that x and y are adjacent (otherwise our graph has no edges!)

4. Since G contains no triangles, neither does A, and by our inductive assumption this implies that there are at most n^2 edges joining vertices in A to other vertices in A.

5. Every point z in A can only be adjacent to at most one of x or y (else x,y,z is a triangle.) Hence there are at most 2n edges joining vertices in A to vertices in B, giving us at most: n^2+2n+1=(n+1)^2 edges in total.

By induction this completes the proof.

 

[kfnmpah]

http://blog.onetravel.com/travel/how-to-say-e2809cthank-youe2809d-in-58-languages.aspx

yep yep yep i will do the odd one myself, i need to practice induction i am terribad at it

u da best!!!

 

[seanieg89]

http://blog.onetravel.com/travel/how-to-say-e2809cthank-youe2809d-in-58-languages.aspx

yep yep yep i will do the odd one myself, i need to practice induction i am terribad at it

u da best!!!

no worries, good luck...some parts of graph theory are pretty fun.

 

[kfnmpah]

yeah, i'm really liking both streams (logic/sets + graph theory) of discrete so far

~i wish it was in the nsw curriculum~

 

[kfnmpah]

ok so i was thinking, the graph under the original conditions (no cycles of 3) has to be bipartite, right? no matter how you arrange the nodes if it satisfies the original conditions it will be bipartite and you could arrange it as a K(1,5) K(2,4) K(3,3) but the maximum number of edges wiill be when it is a K(3,3) graph

so

you have two independent sets, M and N with m(3 in this case) and n(3 again) number of vertices respectively. SO each vertex in M must join up with each vertex in N exactly once
so the total number of edges will just be mxn for any bipartite graph i.e. any graph K(x,y) with x+y nodes the maximum number of edges will be xy then i guess you could guess and check/use combinatorics to figure out which arrangement of nodes in the 2 independent sets will give a maximum value



right?

 

[seanieg89]

ok so i was thinking, the graph under the original conditions (no cycles of 3) has to be bipartite, right? no matter how you arrange the nodes if it satisfies the original conditions it will be bipartite and you could arrange it as a K(1,5) K(2,4) K(3,3) but the maximum number of edges wiill be when it is a K(3,3) graph

so

you have two independent sets, M and N with m(3 in this case) and n(3 again) number of vertices respectively. SO each vertex in M must join up with each vertex in N exactly once
so the total number of edges will just be mxn for any bipartite graph i.e. any graph K(x,y) with x+y nodes the maximum number of edges will be xy then i guess you could guess and check/use combinatorics to figure out which arrangement of nodes in the 2 independent sets will give a maximum value



right?

Yes, the complete bipartite graph K(m,n) has mn edges, and it is easy to show that for fixed m+n that this is maximised when m and n are as close to equal as possible. However, not every graph without triangles is bipartite. As a counterexample consider the 5-cycle.

 

[kfnmpah]

but this graph must be bipartite, yes?

so what i said was

"to satisfy the original conditions, the graph on 6 vertices (or in any general case for the vertex set of some simple graph, G) must be bipartite i.e. n nodes must be split in to two independent sets, A and B, say, with a and b number of vertices respectively.
The maximum number of edges will be achieved if each A subscript i is adjecent to each B subscript j where A and B contain the same number of nodes, or as close as possible*
Each Ai creates exactly 1 edge with each Bj --> the maximum number of edges will be given by a x b

For the original question, the possible bipartite graphs on 6 vertices are K1,5 K2,4 and K3,3 with max edges 5, 8 and 9 respectively
therefore the complete bipartite graph K3,3 will given the maximum number of edges in a simple graph on 6 vertices"


THEN

Max when |a-b| is minimised where a and b are the number of vertices in independent sets A and B respectively
if a=b number of edges = a x b
=ab

if a<b:
number of edges = (a+k)(b-k) where k = some constant such that b<k<a
= ab + kb - ka - k^2
From the definition and conditions of k, ka>kb and ab-k^2<ab
--> (a+k)(b-k) < ab and similarly for b<a
--> maximum number of edges occurs when a=b i.e. the number of nodes in set A = the number of nodes in set B

From this, it can be proven that on a graph with 2n+1 nodes, maximum number of edges without a cycle of 3 will occur when |a-b|=1"


i think most of it is *alright* but what you're saying about a cycle of 5 is getting me like my arguments at the start are probably flawed, yeah?

 

[seanieg89]

but this graph must be bipartite, yes?

so what i said was

"to satisfy the original conditions, the graph on 6 vertices (or in any general case for the vertex set of some simple graph, G) must be bipartite i.e. n nodes must be split in to two independent sets, A and B, say, with a and b number of vertices respectively.
The maximum number of edges will be achieved if each A subscript i is adjecent to each B subscript j where A and B contain the same number of nodes, or as close as possible*
Each Ai creates exactly 1 edge with each Bj --> the maximum number of edges will be given by a x b

For the original question, the possible bipartite graphs on 6 vertices are K1,5 K2,4 and K3,3 with max edges 5, 8 and 9 respectively
therefore the complete bipartite graph K3,3 will given the maximum number of edges in a simple graph on 6 vertices"


THEN

Max when |a-b| is minimised where a and b are the number of vertices in independent sets A and B respectively
if a=b number of edges = a x b
=ab

if a<b:
number of edges = (a+k)(b-k) where k = some constant such that b<k<a
= ab + kb - ka - k^2
From the definition and conditions of k, ka>kb and ab-k^2<ab
--> (a+k)(b-k) < ab and similarly for b<a
--> maximum number of edges occurs when a=b i.e. the number of nodes in set A = the number of nodes in set B

From this, it can be proven that on a graph with 2n+1 nodes, maximum number of edges without a cycle of 3 will occur when |a-b|=1"


i think most of it is *alright* but what you're saying about a cycle of 5 is getting me like my arguments at the start are probably flawed, yeah?

Yeah, the method is flawed unfortunately. As I said, a graph without triangles is not necessarily bipartite.

 

[kfnmpah]

yeah i just realised that- take a simple pentagon, label the vertices 1, 2, 1 ,2 ,1 1 and 1 must be joined but it will still give max edges with no *triangles* as 6, as would a K2,3 graph


fak


whatever i will just write that on my thing, i don't even need to prove anything i just had to draw any graph and say "9" but i wanted to prove it cot damn it

 

[kfnmpah]

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