Graph theory Definition and 175 Threads

Hi everyone, Any help would be appreciated.

Hi everyone. I know this holds for complete graphs, I've proved that by induction. But how can I prove it for graphs which aren't complete? And what is the significance of (2n+1)/3? If a vertex has that degree, does it have some property I should immediately spot?

Let G be a graph of genus g. Let S_g be a surface of genus g (equivalent to the Torus with g handles). The question is: If we embed G on S_g, are the faces that we obtain 2-cells (homeomorphic to disks)? I believe the answer is yes (intuitively). But, is there an argument that is more...

(There isn't a section for Graph Theory, so I figured I'd post this in a spot where a lot of pure math topics are posted). Looking for an easy to read introduction to graph theory book to prep me for a course I'll be taking in the Spring. Nothing too simple, but nothing too in depth (as...

I'm looking for an introductory book on graph theory. I'll be taking a course in graph theory this Spring so I don't want anything too technical, just something to get my feet wet. any recommendations for an easy to follow engaging book? A "for dummies" if you will.

Some background: my friends love to confound me with nonsensical questions, because they know I'm the type of person who cannot let a question go, even if it has no answer, and when I arrive at one, it will be so rigidly logical that no matter how ridiculous it sounds it must be correct. My...

A school class has 90 students, each of whom has ten friends among the other students. Prove that each student can invite three people at a restaurant so that each of the four people at the table will know at least two of the other three. If this had to be translated to a graph it would...

Homework Statement Prove: G is bipartite iff every subgraph H has an independent set containing |V(H)|/2 Homework Equations independent set = set of mutually nonadjacent vertices. The Attempt at a Solution I am trying to understand a solution given by my prof (for the backwards...

Prove that if G is a simple graph with at least two vertices, then G has two or more vertices of the same degree. Pf/ Assume its true for the base case 2 vertices with no edges or 2 vertices with one edge. Then either the degree is of both is 0 or the degree of both is 1. Therefore both...

i need some hints on how to do this problem If a connected planar graph with n vertices all of degree 4 has 10 regions, determine n

When we are young we are taught about two kinds of memory. There is long term memory and their is short term memory. Students are taught to memorize facts though repetition but is repetition of a fact in a 4-8 moth period enough to retain a significant portion of that information over a long...

z = positive int, Y = {1 2 3 ... n} where Y = n greater or equal to z defines Gzn 1)work out a formula in n and z for the edges in G zn, the vertex set to include all possible z elements subsets of Y help please what's the formula? i know how to work out the number of vertices in a formula...

As the title suggest, I do not understand what the difference between isomorphism and equality is in terms of graph theory. I have tried searching the internet but the few definitions I could find for each did not really shed light on the difference. I know that an isomorphism is when there is a...

I'm looking for the title to a popular introductory book on graph theory. For the best possible recommendation, perhaps it would be wise for me to give you signals of my academic maturity. I completed undergraduate math major in May 2010. Since then I've been working, but I'm looking to get...

Homework Statement Let G=A U B be a bipartite graph. For each a in A and for each b in B we have d(a)≥d(b)≥1 where d(v) is the degree of vertex v. Show that there exists a matching which saturates A. Homework Equations The Attempt at a Solution I guess I need to use Hall's...

Homework Statement Prove that if G is a graph of order n such that D(G) + d(G) greater than or equal to n - 1, then G is connected and diam(G) less than or equal to 4. Show that the bound n -1 is sharp. Note: D(G) is the max degree of any vertex in G and d(G) is the min degree of any vertex...

So my course is just getting further and further above my head. I got most of them but I'm stuck on these 3 and have no idea how to start them. This is due friday so hopefully I can get input before that! :) 1) Let G be a (2k + 1)-regular graph, and assume that G - S is still...

Let G be a graph with all its degrees at least three. Show that G contains a cycle with a chord (a chord is an edge which connects two non-adjacent vertices on the cycle). I thought of proving this by induction on the number of vertices of G, but I am stuck. Obviously, n>=4 otherwise it...

Homework Statement Characterize all possible sequences d1; d2; : : : ; dn so that there exists a forest with vertex set fv1; v2; : : : vng with deg(vi) = di. (So, you should nd a statement of the form: a sequence d1; : : : dn comes from a forest if and only if ... ) I emailed him and...

Need help ! – Graph Theory Hello, I have recently started studying “Graph Theory” but i find it very difficult. I'm still not good in this course. So I hope you can help me with the following task: G=(V,E) is undirected (no oriented) graph. We need to find the number of all components...

Homework Statement Prove the following: If the tournament graph is acyclic, there is exactly one vertex which got edges more than any vertex in the graph. Homework Equations A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected...

Let u and v be distinc vertices in a connected graph G. There may be several connected subgraphs of G containing u and v. What is the minimum size of a connected subgraph of G containing u and v? and does this suggest another question?

How to prove that the number of edges in a simple bipartite graph with n vertices is at most n^2/4? Definition of bipartite graph: a graph whose vertex-set can be partitioned into two subsets such that every edge has one endpoint in one part and one endpoint in the other part. I try to...

Hi all, This is my first post to this forum, so allow me to introduce myself. I am a 28 year old person who is about to start a Phd in Machine learning with focus on graph theory. Now from my preliminary research, it seems that theory developed has a lot of use in computational biology...

Homework Statement Prove that a graph is a tree if and only if it has no cycles and the insertion of any new edge always creates exactly one cycle. The Attempt at a Solution Assume that a graph G is connected and contains no vertices with a degree of zero. So would I get my proof by...

Homework Statement For any simple Graph G of maximal degree X, let U be the set of nodes that do not span any vertice in G. prove that |U| \geq \frac{n}{X+1} The Attempt at a Solution First we notice that |U| is minimized when G is X-regular, i.e. that every node is connected to...

Homework Statement Prove that, if G is a simple graph with no K5-minor and |V(G)| Does not = 0, then G has a vertex at most 5. Homework Equations |E(G)| <= 3|V(G)| - 6 for |V(G)| >= 3 (Proved by earlier part of problem set) Handshake theorem (I don't believe we are allowed to use...

Homework Statement The complement of T' of a tree T with n vertices has [(n-1)(n-2)]/2 edges, for all integers n greater than or equal to 2. Homework Equations Must prove using induction and using Lemma 18.2 which states "any tree that has more than one vertex has at least one vertex of...

Homework Statement Starting in the bottom left corner and moving either up or right, one square at a time, adding up the numbers along the way, what is the largest sum that can be made once you have reached the top right corner 142212 431343 214212 122331 413121 314342 211113 342322 This is...

Homework Statement Let G be a graph of order n and size m. V(G)={v1,v2,...,vn} and deg(vi)=ri. Find a formula for the size of the line graph L(G) in terms of n, m, and ri. Homework Equations The http://en.wikipedia.org/wiki/Line_graph" L(G) is the graph such that every vertex in L(G)...

I am working on graph theory assignment. I need help because I am not seeing where I am going with this question. Here's the question: G is a simple graph with n vertices. -> show that vertex colouring of G [ X(G) ]* vertex colouring of G complement >= n -> show that the vertex...

Homework Statement Sorry about the basic question, I haven't takena course on graph theory yet but need this for a course in computer science. The problem: Write a program whose input is an adjecancy matrix and whose output is the number of cycles of length 3 and 4. The Attempt at a...

I'm in my 4th year of a physics program, and I've got some serious freedom choosing courses now. Has anyone taken graph theory? I've got a basic idea what it is, but no clue how difficult it might be. Any other good math courses to take as an option that won't bee too difficult? For...

I have a problem involving graph theory. This is not a graph theory course though so I do not know much about it. If we have complete bipartite graphs consider whethere or not they are graceful. A graph is graceful provided the vertices of the graph can be assigned v distinct integers...

Homework Statement If all vertices of planar graph have degrees greater than 4, prove if that graph has at least 12 vertices with degree of 5. Homework Equations d1+d2+...+dn= 2*m (m - number of edges, di-degree of i-vertex) f=2-n+m, f - number of faces, n-number of vertices The...

Hi Is graph theory a more pure or applied subject? I thought it was pure but now I am confusing myself because it has so many applications. Thanks

http://www.win.tue.nl/~aeb/srgbk/node10.html Under the 'For connected graphs all is clear from above' I've been asked to prove this for connected graphs, but I don't see how this is so clear? Can anyone help me? Thanks

I'm wondering, is it possible a graph G and its complement G' to be complete?

Hello I imported a 30 X 30 matrix into Mathematica. I made a graph out of this and then found the minimum spanning tree. Next, I printed off a list of the edges. I included the edgeweight option to get the associated weights listed next to each edge. My goal was to ultimately sum these...

Homework Statement Let G be a graph with at least two vertices, such that the cut induced by every proper nonempty subset of vertices of G contains exactly two elements. Determine (with proof ) the number of vertices and edges in G. Homework Equations Connectedness. A graph G is...

Homework Statement Let G be a non-empty graph of order n whose vertices have degrees d1, . . . , dn. The line graph of G is defined as follows: the vertices of L(G) are the edges of G, and two vertices of L(G) are adjacent if they share an endpoint in G. Prove that the size of L(G) is...

If G is a connected graph with a cut-vertex v and G1 is a component of G-v, then show that the induced subgraph <V(G1)U{v}> of G need NOT be a block of G. I guess all I would need is a counterexample, but I can't come up with one.

I am planing to take a course in Graph theory at my university, but i have no idea what it is. I want to take something that is ,to some extent, rigorous and interesting. This is the course summary provided by my school : Introduction to graph theory and its applications with an emphasis on...

Homework Statement Hello everyone; This is the problem that I am working on: (a) - Show that in every graph there are two vertices of the same degree. (b) - Determine all graphs with exactly one pair of vertices of equal degree. Homework Equations None. The Attempt at a...

First and foremost, let's get something straight before I post my proof: I'm not enrolled in any classes. I don't have any class money. Though my grades were strong enough for grad school, I don't think I would've made a good mathematician. I'm just not good enough. I thought I was done with...

The graph theory HELP! How many distinct graphs can be found by the set V={1,2,...,n} with k edges? For this question i conclude that totao.l number of distinct graphs comes with 2^(choose two in n) but i cannot find the solution which gives the relation with k edges can you help me?

[b]1. Suppose a graph has nine vertices each of degree 5 or 6. Prove that at least five vertices have degree 6 or at least six vertices have degree 5. Homework Equations [b]3. I'm pretty sure that I need to use the Pigeonhole Principle to solve, but don't know where to go from there.

I was wondering if I could get some help with the terminology when it comes to graph theory. In this picture : http://en.wikipedia.org/wiki/Image:6n-graf.svg the numerical values are vertices (or nodes as some call it), so what are the edges then (are they the lines that connect the nodes)...

Hello! This question seems simple but I think I'll need your help to prove it. Prove that if there are vertices x and y in V(G) such that G contains three independent x-y paths then G contains an even cycle. Thank you in advance.

prove : Let G be a graph that has exactly 2k vertices of odd degree. Show that there are k edge-disjoint paths each of which joins a different pair of ver- tices of odd degree. I have to prove this with induction on k. There is a hint that I need to strenghten my induction hypothosis but I...