Prove tht a simple graph with 'n' vertices&'k' components can hv atmost{(n-k)(n-k+1)/2} edges?
922060
My suspicion upon seeing this question is that it can be solved using mathematical induction.  After all, couldn't we simply 'build' such a (maximally connected) graph starting with n=2 vertices and 'grow' it from there?\n\nRather than take on the proof myself -- mostly because I am unsure of the definition of 'components' -- I leave it as an exercise for you.  However, it bears noting that the formula shown is the commonly accepted "sum of the first n integers" formula used in almost every text on induction.\n\nGood luck!
94604
A quotation from\nhttp://www.ams.org/featurecolumn/archive/sylvester3.html\n\n"In retrospect, it is clear that one could easily see that there had to be at least three ordinary lines for any point-line configuration. This follows from Melchior's work. Later it was shown that the number of ordinary points had to grow larger as the number of points in a plane finite configuration grew. Both G. Dirac and T. Motzkin were among those who explicitly conjectured that there would be at least n/2 ordinary points for a set of n plane points. However, it should again be noted that for n =7 and 13, there are configurations for which this bound does not hold. The additional requirement that n be large enough has to be added. It was announced by Hansen that he had a proof that there were always at least n/2 (n > 13), but the proof, unfortunately, had an error. Despite this, there were many correct new results in Hansen's investigations related to Sylvester-Gallai results. The number of ordinary points is known to be at least 3n/7 (n > 2), as was shown by L. Kelly and W. Moser, and the best known result (due to J. Csima and E. Sawyer) is that the number of ordinary lines is at least 6n/13 (n > 6). "
1065017
I'm writing up a proof right now that this is not possible.\n\nCheck out the pdf at:\nhttp://www.geocities.com/euleratuo/
769753
Without knowing the relationship between successive elements, I think the best you can do is this:\n[k=0, n-1]∑(x_(k+1) - x_k)²\n[k=0, n-1]∑(x_(k+1)² - 2x_k*x_(k+1) + x_k²)\n[k=0, n-1]∑x_(k+1)² - 2[k=0, n-1]∑(x_k*x_(k+1)) + [k=0, n-1]∑x_k²\n[k=1, n]∑x_k² - 2[k=0, n-1]∑(x_k*x_(k+1)) + [k=0, n-1]∑x_k²\n\nx_0 + x_n + 2[k=1, n-1]∑x_k² - 2[k=0, n-1]∑(x_k*x_(k+1))
775741
I cannot prove it formally but I can mention the steps\n\na | u(n)\n\na | u(n+1)\n\nso a | u(n+1) - u(n) if a devided b and a devided c then it devides b-c\n\nso a | u(n-1)\n\nthere by we reach a | u(0) and a|u(1)\n\nu(0) does not give any infomation as u(0) =0\n\nso a | u(1) = 1\nso a= +/-1 \nu(0) = 0\nu(1)  = 1\n\nnext terms are u(2) = 1,u(3) = 2 ,u(4) = 3, then 5,8,13,
727062
K1= 1/2 m v ^2\nK2 = 1/2 m (1/2 v) ^2 = 1/8 m v ^2\n\nK1 = 4 K 2\n\n\nb. 4 times
669580
-E-N-G-L-A-N-D- 2 POINTS
196942
wow, that's pretty amazing.  i was convinced that was wrong until i tried drawing the "counterexample" i had in my head.  other than reading through that proof (props to the guy who posted that link, btw) i guess the best way to realize this is true is to show that for any five closed shapes in two dimensions, there will always be at least two shapes that do not touch one another.  because of this, you can color those two shapes the same color, so you will have a maximum of four colors.\n\nthis problem is reducible to a graph with five nodes, where each node represents a shape and each edge represents a shared boundary.  (showing that this is reducible to this is probably the difficult part of the proof, which is why i'm glossing over it).  you cannot connect each node to every other node without there being at least one set of intersecting edges.  if edges intersect, it indicates that the shapes (or countries) represented by the two nodes connected by one of the intersecting edges do not share a border.\n\nhere's my suggested proof (assuming we accept the reduction to this graph problem):\nstart with a graph G with three nodes, {A, B, C}.  There are also edges {AB, BC, AC}.  So, G is a closed graph with three nodes and three edges where each node is connected to each other node in the graph (i.e. G is a triangle).  If our reduction of the coloring problem is correct, then there exists a map reducible to this graph that requires three colors to be colored in the described way.\n\nNext, construct a graph H by adding a node D to graph G.  There are two possible ways to add D: 1) D can be on the interior of closed graph G; or 2) D can be outside the interior of G.\n\nIn case 1, let the new graph with nodes A,B,C,D be called H.  We need to show that we can make H such that D is connected to A, B, and C without any intersecting edges.  This is simple enough; straight edges to A, B, and C from D do not intersect each other or the existing edges of the graph G.  So, H demonstrates that a map can require four colors.  H now has four separate enclosed interior regions: triangles ABD, ACD, BCD, and ABC.\n\nFrom H, construct a graph I by adding another node E.  Repeating the above procedure, E can be placed in four places: a) in the interior of ABD; b) in the interior of ACD; c) in the interior of BCD; or d) on the exterior of ABC.\n\nCASE a: As with constructing H, edges can be drawn from E to A, B, and D.  However, C is on the exterior of ABD, so any edge from E to C must cross either AB, BD, or AD.  So, in case a, there must be an intersection, so four colors is still an option.\nCASES b and c follow similarly.\nCASE d: E is on the exterior of ABC, but D is on the interior of ABC.  Any edge between E and D must intersect AB, BC, or AC.  So, coloring with four colors is possible in this case.  Since it is possible in all cases, it is possible for any map with five regions with a sub-map reducible to a graph like H.\n\nCase 2) Instead of placing D in the interior of G, make a graph H' by placing D on the exterior of triangle ABC.  Any quick drawing will show that D is easily connected to A, B, and C.  So there is a map with four regions that requires four colors.  To make the rest of this easy, note that H' also produces four enclosed regions: ABD, ABC, BCD, and ADC.  I won't go through the trouble to prove this, but clearly H' is isomorphic to H.  That being said, whatever is true of the general graph H is also true of the general graph H'.  Therefore, a graph I' made by adding a node to H' cannot be complete without there being at least one set of intersecting edges.\n\nSince this is true for all cases, any map reducible to a graph with five nodes is colorable with just four colors.  QED\n\nSorry this is so long.  I hope it's helpful.
293210
the graph of |x - 2| + |y - 5| = 5 consists of four lines which are graphs of the following functions:\nx-2+y-5=5 which is  line A: x+y=12\n-x+2-y+5=5 which is line B: x+y=2\n-x+2+y-5=5 which is line C: x-y=-8\nx-2-y+5=5 which is line D: x-y=2\nnext thing to do is graph these four lines. the easiest way is to find the 0s. \nline A: x+y=12\n        x=0 y=12 point A1(0,12)\n        y=12 x=0 point A2(12,0)\nline B:  x+y=2\n         x=0 y=2 point B1(0,2)\n         x=2 y=0  point B2(2,0)\nline C: x-y=-8\n         x=0 y=8 point C1(0,8)\n         x=-8 y=0 point C2(-8,0)\nline D: x-y=2\n        x=0 y=-2  point D1(0,-2)\n        x=2 y=0   point D2(2,0)\nthese four lines enclose a figure that is a rectangle. lets find the length of each side. after you plot the four lines you will notice that line x+y=12 intersects with line x-y=2 lets call the intersection point I1 to find I1 coordinates we rearrange y=12-x and y=x-2 and from y=y we get x-2=12-x or 2x=14 or x=7 if x=7 y=12-7=7-2=5 the point I1 is I1(7,5).\nline x+y=12 also intersects with line x-y=-8. Lets call this intersection point I2. to find coordinates we have y=12-x and y=x+8 y=y or 12-x=x+8 or 2x=4 or x=2 for x=2 y=12-2=2+8=10 so the point is I2(2,10) \nside I1I2 of the rectangle length is side a. to find length of a we do\na^2=(7-2)^2+(10-5)^2=25+25=50\na=sqrt(50)\nwe need the second side, lets call it b.\nto find length of side b we need at least one more point. lets find intersection of x-y=2 and x+y=2 and call it point I3. y=x-2 and y=2-x or x-2=2-x or 2x=4 or x=2. for x=2 y=2-2=2-2=0 point I3(2,0)\nside b:\nb^2=(7-2)^2+(5-0)^2=50\nb=sqrt(50)\nit means a=b or our rectangle is a square!\nso the area of the square is Area=side^2 since our square&#92;s side is a=b=sqrt(50), the area is 50.\nI hope this helps, I really don't have time to explain it in more details.
1129079
Consider a vertex v in the graph.\n\nSince it has degree at least floor(p/2), it is connected to at least floor(p/2) other vertices.  So the component of G that contains v is made up of at least floor(p/2) + 1 vertices.  \nHow many vertices could not be in this component?  Well, at most (p - floor(p/2) -1).  And this quantity is <= floor(p/2).\nBut we know that any vertex is in a component of at least size floor(p/2) + 1, so there must actually be 0 verticies not in the component that contains v.\nThus, G is connected.
323669
Well, this isn't true, actually.  The graph on six vertices consisting of two connected components, each a triangle, is 2-regular but not hamiltonian.  This isn't even true for connected 4-regular graphs.  For example, take two copies of the Petersen Graph (go to Mathworld if you don't know what this is) and add 10 edges joining vertices in one copy with their "twin" vertex in the other copy.  This graph is 4-regular and not hamiltonian.
703879
This sounds like plane geometry where you have an n sided polygon and want to know how many diagonals you can draw.  From each vertex, you can draw a diagonal to every other vertex except to yourself and the two next to you (those two line make sides of the polygon not diagonals).  So for n sides (which means n vertices), you can draw n-3 diagonals at each vertex.  This gives (n-3)*n.  But this just counts the starting end of each line. Whenever you draw one of these lines, it goes to another vertex.  If we drew (n-3)*n lines, we would traces over each diagonal twice, once from each end so there are only half as many diagonals as that.\n\nThe answer then is: (n-3)*n/2
636496
Sure. You just need a set of vertices and a set of edges (directed edges in case of a directed graph). There's no requirement for the set of edges to be non-empty. \n\nSometimes even an empty set of vertices is allowed.
432121
This is a graph theory problem.\n\nRepresent each person by a point, connect every point with every other point. Color the line red if the people know each other, blue if they don't.\n\nThe question now can be stated, that there is at least 1 red triangle, or one blue triangle. \n\nLabel the points p1, p2, .. p6.\n\nLook at p1. p1 is connected to the five other points. At least 3 of the lines must be the same color say red. With out loss of generality, we can all the points connected to p1 by red lines p2, p3, and p4.  If any pair of p1, p2, and p3 are connecte with a red line, we have a red triangle formed.\n\nIf not then p2, p3, and p4  form a blue triangle.
1128311
Differential geometry/manifolds, Optimization word problems in 3D, topology proofs.
147899
Here is a graph and some explanation:\nhttp://mathworld.wolfram.com/Tetrahedron6-Compound.html
147821
- -----------O\n------------ . .-----------  _\n  K+ ( O: Mn  :O )\n-------------. .\n------------ O\n\nomit the long dotted lines