Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

4
votes
2answers
438 views

Returning Paths on Cubic Graphs Without Backtracking

I was once interested in the returning paths on cubic graphs . But I'm even more curious to have the number of ways without backtracking, which means doing one step forward and than one back (which ...
10
votes
2answers
275 views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
7
votes
2answers
2k views

How to construct a k-regular graph?

I have a hard time to find a way to construct a k-regular graph out of n vertices. There seems to be a lot of theoretical ...
3
votes
1answer
2k views

How can I find the number of the shortest paths between two points on a 2D lattice grid?

How do you find the number of the shortest distances between two points on a grid where you can only move one unit up, down, left, or right? Is there a formula for this? Eg. The shortest path between ...
4
votes
5answers
5k views

Given a simple graph and its complement, prove that either of them is always connected.

I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph. Well, I always post my attempt at solution, but here I'm totally ...
20
votes
9answers
6k views

What are good books to learn graph theory?

What are some of the best books on graph theory, particularly directed towards an upper division undergraduate student who has taken most the standard undergraduate courses? I'm learning graph theory ...
0
votes
1answer
266 views

Constructing a graph from a degree sequence

Let's say I'm given several degree sequences like {4,3,3,2,2} {3,3,3,3} {5,3,3,2,2,1} I can find the number of edges using the handshaking lemma But how do I construct a graph just given these ...
0
votes
2answers
614 views

Help with graph induction question?

Given a graph $G$ with $n$ vertices, where $n$ is even, prove by induction that if every vertex has degree $n/2 + 1$, then $G$ must contain a 3-cycle. A 3-cycle is a set of 3 vertices, $a; b; c$ such ...
26
votes
6answers
2k views

Motivation for spectral graph theory.

Why do we care about eigenvalues of graphs? Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so ...
6
votes
4answers
2k views

3 Utilities | 3 Houses puzzle?

There's a puzzle where you have 3 houses and 3 utilities. You must draw lines so that each house is connected to all three utilities, but the lines cannot overlap. However, I'm fairly sure that the ...
6
votes
1answer
2k views

How to prove that a simple graph having 11 or more vertices or its complement is not planar?

It is an exercise on a book again.If a simple graph G has 11 or more vertices,then either G or is complement $\bar { G } $ is not planar. How to begin with this?Induction? Thanks for your help!
6
votes
1answer
285 views

Known bounds and values for Ramsey Numbers

Is there a good online reference that lists known bounds on Ramsey numbers (and is relatively up to date)? The wikipedia page only has numbers for $R_2(n,m)$. I am specifically interested in known ...
2
votes
1answer
115 views

associativity in graph theory

Can anybody help me in clearing the facts how the associativity was proved in cartesian product of 3 graphs, and thus showing isomorphism. I can easily solve for the case when its two graphs. Taking ...
0
votes
2answers
2k views

Prove Petersen graph is not Hamiltonian using deduction and no fancy theorems

Prove Petersen graph is not Hamiltonian using basic terminology and deductions. I'm looking for an explanation without k-colouring or anything fancy like that since I haven't covered that in class. ...
34
votes
7answers
27k views

Online tool for making graphs (vertices and edges)?

Anyone know of an online tool available for making graphs (as in graph theory - consisting of edges and vertices)? I have about 36 vertices and even more edges that I wish to draw. (why do I have so ...
15
votes
9answers
6k views

Graph theory software?

Is there any software that for drawing graphs (edges and nodes) that gives detailed maths data such as degree of each node, density of the graph and that can help with shortest path problem and with ...
16
votes
2answers
794 views

Not lifting your pen on the $n\times n$ grid

The question I am asking has basically already been asked. Please see this MSE thread. There are a few questions brought up on that thread, and a smaller number were answered. The reason I am ...
11
votes
2answers
4k views

Understanding the properties and use of the Laplacian matrix (and its norm)

I am reading the wikipedia article on the Laplacian matrix: http://en.wikipedia.org/wiki/Laplacian_matrix I don't understand what is the particular use of it; having the diagonals as the degree and ...
14
votes
1answer
347 views

What are all conditions on a finite sequence $x_1,x_2,…,x_m$ such that it is the sequence of orders of elements of a group?

My Definition: The finite sequence $x_1,x_2,...,x_m$ of nonnegative integers, is said to be generated by the finite group $G$ iff $n:=|G|=x_1+x_2+...+x_m$. $n$ has $m$ divisors. if ...
5
votes
1answer
347 views

Rank of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
4
votes
1answer
336 views

eigen decomposition of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
9
votes
1answer
5k views

How many non-isomorphic graphs with n vertices and m edges are there?

Could someone tell me how to find the number of all non-isomorphic graphs with $m$ vertices and $n$ edges. (The graph is simple, undirected graph) In my particular problem, $m =20, n=180$ Attempt at ...
4
votes
1answer
504 views

Sum of the shortest paths in graph

Let $ d_{G} \left(x,y \right) $ be the length of the shortest path between the vertices $x$ and $y$ in graph $G$ and let $s\left(G\right) = \sum_{x,y \in V \left[G\right]} d_{G} \left(x,y \right)$ . ...
8
votes
1answer
455 views

What is the significance of the graph isomorphism problem?

It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an ...
6
votes
4answers
2k views

why a complete graph has $\frac{n(n-1)}{2}$ edges?

i'm studing graphs in algorithm and complexity, (but i'm not very good at math) as in title, why a complete graph has $\frac{n(n-1)}{2}$ edges? and how this is related with combinatorics?
3
votes
2answers
262 views

A less challenging trivia problem

There are 25 people sitting around a table and each person has two cards. One of the numbers 1,2,..., 25 is written on each card, and each number occurs on exactly two cards. At a signal, each person ...
3
votes
2answers
421 views

In a graph, the vertices can be partitioned $V=V_1\cup V_2$ so that at most half of all edges run within each part?

I am thinking of destroying all cycles of odd length by removing edges, so that I get a bipartite graph, with a partition $V_1$ and $V_2$ so that no edge in the new graph run within the two parts. ...
1
vote
1answer
202 views

Rank of a graph matrix

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
6
votes
1answer
338 views

For a graph $G$, if $m>\binom{n-1}{2}$, then $G$ is connected

I'm trying to pick up a little graph theory out of Bondy and Murty's Graph Theory as suggested here. Problem 1.1.12 has given me a little hitch. Let $G$ be a simple graph of order $n$ and size ...
4
votes
3answers
729 views

Short proof for the non-Hamiltonicity of the Petersen Graph

It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either. Is there a simple (short) argument that the ...
4
votes
1answer
3k views

Powers of Adjacency Matrix (Determination of connection in Graph)

I am studying graph theories, and I am not sure about how power of adjacency works. I know $k$-th powers of A tells connection in graph, and I can read lengths between a vertex to vertex after taking ...
4
votes
2answers
539 views

How to find chromatic number of the hypercube $Q_n$?

How to find chromatic number the hypercube $Q_n$? I know $\chi(Q_2)$=2 , $\chi(Q_3)$=2 , $\chi(Q_4)$=4
2
votes
2answers
209 views

Matrix graph and irreducibility

How do I prove that if $A\in\mathbb C^{n\times n}$ is a matrix then it is irreducible if and only if its associated graph (defined as at Graph of a matrix) is strongly connected? Update: Seeing as ...
2
votes
1answer
250 views

Proving bipartition in a connected planar graph

Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite. Any hints/tips will be greatly appreciated.
2
votes
2answers
519 views

Coloring Graph Problem

If G is a graph containing no loops or multiple edges, then the edge-chromatic number $X_e(C)$ of G is defined to be the least number of colours needed to colour the edges of G in such a way that no ...
1
vote
3answers
96 views

Solution of a recurrence with varying coefficient

Please help me to find the solution of the recurrence in terms of n(implies $(f(n))$ and also the summation of the recurrence up to infinity ($sum = \sum_{n=0}^\infty f(n)$) . ...
1
vote
2answers
194 views

Regular graph (Homework)

Let $G = (V, E)$ be a graph and $ad(G) = \frac{2|E|}{|V|}$ the average degree of $G$. $$ mad(G) = max ( ad(H) : H \le G ) \text{ the maximum average degree of a subgraph of $G$} $$ We know that ...
1
vote
1answer
174 views

Returning Paths on Cubic Graphs

Suppose we have a 3-edge-colorable cubic graph with $N$ vertices. How many paths of length $N$ exist that return to its origin? Or putting it differently: What is "Pólya's Random Walk Constant" on ...
1
vote
1answer
243 views

eigen decomposition of an interesting matrix (general case)

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
0
votes
1answer
381 views

Counting graphs with even degrees! Trouble with formula!

There is one topic about "Counting graphs with even degrees" here that tell something about edge space, vector space, cut space and ... I have a graph exam tomorrow, and there is a problem that said ...
0
votes
1answer
253 views

Calculating powers of 2 on a 2D grid without factoring.

Consider the following 2D infinitely large grid where the dots represent infinity: ...
8
votes
3answers
830 views

Free Graph Theory Resources

What freely available graph theory resources are there on the web? In particular, I am interested in books and lecture notes containing topics such as trees, connectivity, planar graphs, the ...
14
votes
3answers
286 views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
9
votes
2answers
318 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
9
votes
1answer
2k views

What condition need to be imposed on Havel-Hakimi theorem to check for connected graph?

Havel-Hakimi Theorem: A sequence s: $d_1, d_2, \ldots, d_n$ of non-negative integers with $\Delta = d_1 \geq d_2 \geq \ldots \geq d_n$ and $\Delta \geq 1$, is graphical if and only if the ...
6
votes
2answers
368 views

Lower bound on number of edges in “triangular” graph

Question I found in one of the previous year's exam: Let $G$ a connected graph on $n \geq 3$ vertices, such that every edge participates in at least one triangle. Prove that $|E(G)| \geq ...
5
votes
2answers
846 views

connection between graphs and the eigenvectors of their matrix representation

I am trying to learn graph theory and the linear algebra used to analyse graphs. The texts I have read through have lots of lemmas and theorems proved. The proofs are convincing but I fail to see the ...
7
votes
4answers
4k views

How to calculate the number of possible connected simple graphs with $n$ labelled vertices

Suppose that we had a set of vertices labelled $1,2,\ldots,n$. There will several ways to connect vertices using edges. Assume that the graph is simple and connected. In what efficient (or if there ...
7
votes
7answers
725 views

How many countable graphs are there?

Even though there are uncountably many subsets of $\mathbb{N}$ there are only countably many isomorphism classes of countably infinite - or countable, for short - models of the empty theory (with no ...
6
votes
4answers
506 views

4-Color Theorem on Surfaces

Is it true, that the minimum number of colors to color a map is still 4, even if the surface you draw the map upon is more complex than a sphere? What if we have “Planar” graphs on Möbius strips or ...