Graph theory Definition and 156 Threads

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...

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...

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 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 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...

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...

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...

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...

Homework Statement Prove by induction that the graph of any triangulation of a polygon will have at least 2 vertices of degree 2 Hint: Split the triangulation graph into 2 triangulation graphs at some chord e The Attempt at a Solution Ok I am pretty terrible at induction proofs...

Homework Statement Show that for any connected graph we have the |V(G)|-1 <= |E(G)| The Attempt at a Solution There exists a longest path in the connected graph, call H. It has |E(H)|+1>=|V(H)|. For the other parts of the graph, in order to minimise the number of edges we have all other...

From the definition of a graph, it dosen't mention anything about a pictorial graph. Things are only dealt with set wise so it is possible to do graph theory without graphs? It would be extremely unnatural though.

I'm doing to come up with a subject in either of them to do either an "independent study" or "project" on, the former is a course which simply requires you to learn the subject and the latter is "independent study" + a x-page paper. Unfortunately I don't know either subject too well so I can't...

Homework Statement http://en.wikipedia.org/wiki/Dual_graph I am trying to show that if a graph G is connected, then each face of its dual graph G* contains exactly one vertex of G. Homework Equations The Attempt at a Solution I tried counting the vertices in G and the faces in...

Hi! I was given the following task: It's not very difficult to draw the graphs: http://i83.photobucket.com/albums/j315/dobry_den/graphs.jpg but i can't think of how i would argue... Do you have any idea? Thanks in advance!

i read a little bit of the syllabus in my university graph theory course and i just wonder if the the kirchhoff theorem in graph theory has any application to kirchhoffs law in direct current in electricity?

My complete layman's question. In two of Smolin's books as well as in popular science journals I read that there is the idea of a discrete space, i.e. space would not be completely continuous but rather have "smallest pieces". I wonder if this means that space can be modeled as a graph (the...

Hi, I have this problem I don't understand I have been on it for days now: Show that the existence of a simple circuit of length k, where k is a positive integer greater than 2, is an isomorphism invariant. please can someone help me with it? Thank you B.

I remember when I was taking discrete analysis of data structures and we had to prove certain graph theory properties. I'll give a specific example, prove that the cycle graph, C_n, is connected for all n. From what I remember, it was induction we used to prove this...what I want to know...

These questions deal with polygonal guarding: a) Suppose P is a simple polygon where g(P) = 2. Prove or disprove that P can always be guarded by two guards that can always see one another (ie the definition of visibility, but not clear visibility) To disprove all is needed is a...

Graph Theory -- How do I construct this graph? I have a question which I think I'm supposed to solve using graph theory. Here's the problem statement: "Given 6 people, suppose that the relationship between them is that they are either friends or complete strangers. Show that there must be...

Can anyone explain to me the graph theory and its applictations.

a professor posed the following question in class: Is it possible for a knight to move around an 8x8 chess board so that it makes every possible move exactly once? (consider a move between two sqaures connected by a knight to be completed when the move is made in either direction) so i...

hey guys I am taking a class right now called Finite Mathematical Structures, and I am having a pretty tough time. although it's only about 1 - 2 weeks into the semester, i am having a hard time actually understanding graph theory problems. so far we are doing isomorphisms, edge coverings...

Hey everyone, I wasn't sure where to put this, since graph theory doesn't really have it's own name here (we don't even have a combinatorics or discrete math category...), so I decided to just put it here in "General Math". My question pertains to degree sequences of graphs. I'm asked to...

I am not really sure how to start this problem, and I have tried searching everywhere. If you could help me that would be great...just to know how to get started. I'm in 2nd Year, Intro to discrete mathematics, if it matters. Thanks Let G be a graph whose vertices correspond to the...

what's the difference between a subgraph and an induced subgraph? looking here: http://mathworld.wolfram.com/InducedSubgraph.html how is the figure K8 ? isn't that K10 ?? also, what is a spanning subgraph?