Graph theory Definition and 156 Threads

I'm not sure where to post this, but anyway here is the question: Given a graph G(p,q) is a tree where p is the number of vertices and q is the number of edges. Since given graph is a tree, number of edges q=p-1. How do you prove that every non-trivial tree has atleast two vertices with...

I'm having an exam on graph theory next week and I'm having some problem with understanding the meaning of calculating eigenvalues of adjacency matrices for graphs. My notes suck from the lectures and I'm totally lost... Our professor asked "What is the sum of elements in row k of the...

Hello, Does anyone know of an online resource which explains Dijkstra's Algorithm both in tabular form and graphical form? My text does an incredibly poor job explaining this algorithm. I sort of understand it graphically. But I have absolutely no idea what is going on when it comes to...

Hello, I am having trouble understanding the definition of components and connectivity. Here is the definition I have been given in my text: Alright, I know that a subgraph is a subset of vertices and edges which itself forms a graph. I also know that a path is a subgraph in which no edge...

Hello, My discrete math course has begun a section on graph theory. And I am hung up on some of the definitions. If someone is familiar with graph theory, I would appreciate it if some of these definitions could be reworded in another way. I will post the definitions we have taken so far and...

does anyone have an idea on proving that there is a triangle-free k-chromatic graph for every positive integer k? or, how to prove that given a simplicial ordering on a chordal graph G, running the greedy coloring algorithm on the reverse order gives the optimal coloring on the complement...