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

5
votes
3answers
663 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 ...
11
votes
2answers
465 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 ...
1
vote
2answers
451 views

Could one be a friend of all?

The social network "ILM" has a lot of members. It is well known: If you choose any 4 members of the network, then one of these 4 members is a friend of the other 3. Proof: Is then among any 4 ...
8
votes
10answers
3k 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 ...
4
votes
2answers
3k views

How many connected graphs over V vertices and E edges?

Is there a way to calculate the number of simple connected graphs possible over given edges and vertices? Eg: 3 vertices and 2 edges will have 3 connected graphs But 3 vertices and 3 edges will have ...
31
votes
16answers
17k 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 ...
9
votes
2answers
3k 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
3k 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 ...
2
votes
2answers
716 views

If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?

Any help would be appreciated. If $n$ is a natural number $\ge 2$ how do I prove that any graph with $n$ vertices has at least two vertices of the same degree?
5
votes
5answers
9k 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 ...
2
votes
1answer
757 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 ...
35
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 ...
0
votes
2answers
1k 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 ...
19
votes
11answers
9k 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 ...
10
votes
4answers
7k 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 ...
8
votes
4answers
9k views

Proof a graph is bipartite if and only if it contains no odd cycles

How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.
6
votes
2answers
3k views

Show that there's a minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example ...
0
votes
2answers
248 views

When a 0-1-matrix with exactly two 1’s on each column and on each row is non-degenerated? [1]

Let $A$ be an $n\times n$ matrix with entries in the set $\{0,1\}$ which has exactly two ones in each column and two ones in each row. Give necessary and sufficient conditions for the rank of $A$ to ...
2
votes
2answers
986 views

Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself ...
10
votes
2answers
203 views

How many directed graphs of size n are there where each vertex is the tail of exactly one edge?

In a research problem in an unrelated area, me and a student found it necessary to count the number of directed graphs with every vertex having one outward-pointing edge, with no restrictions on the ...
6
votes
1answer
3k 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
334 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 ...
4
votes
2answers
707 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 ...
4
votes
1answer
366 views

Fastest way to try all passwords

Suppose you have a computer with a password of length $k$ in an alphabet of $n$ letters. You can write an arbitrarly long word and the computer will try all the subwords of $k$ consecutive letters. ...
2
votes
1answer
188 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 ...
1
vote
2answers
3k 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. ...
49
votes
15answers
53k 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 ...
14
votes
2answers
5k 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 ...
18
votes
2answers
885 views

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

Does there exist $n$, and $r<2n-2$, such that the $n\times n$ square grid can be connected with an unbroken path of $r$ straight lines? Note: This has essentially already been asked - see this ...
15
votes
1answer
397 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 a finite group $G$ iff $n:=|G|=x_1+x_2+\cdots+x_m$. $n$ has $m$ divisors. if ...
8
votes
1answer
589 views

Upper bound on $\chi(G)$ for a triangle-free graph

I'm struggling with the following question; For every graph $G$ such that $K_3 \not\subseteq G$ (i.e. $G$ does not contain a triangle), prove that $\chi(G) \leq 2\sqrt{n} +1$ (where $\chi(G)$ ...
9
votes
4answers
421 views

How many “good” graphs of size $n$ are there?

Let's a call a directed simple graph $G$ on $n$ labelled vertices good if every vertex has outdegree 1 and, when considered as if it were undirected, it is connected. How many good graphs of size $n$ ...
5
votes
1answer
361 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
362 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 ...
10
votes
1answer
7k 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
621 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)$ . ...
9
votes
1answer
843 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 ...
9
votes
4answers
3k 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?
6
votes
3answers
385 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
5
votes
1answer
5k 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
1answer
155 views

A partition of vertices of a graph

I've got an example for this question, but there are many different possibilites and I don't know how to show this for all graphs. Has got anyone any advice how to begin ? Let $G=(V,E)$ be an ...
3
votes
2answers
354 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
695 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. ...
2
votes
1answer
231 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
2
votes
2answers
2k views

Proof that any simple connected graph has at least 2 non-cut vertices.

I'm trying to prove that any simple connected graph with at least $3$ vertices ($|V| \ge 3$) has at least $2$ vertices whose removal will not lead to the increment of number of components. In other ...
1
vote
2answers
114 views

Maximum no.of edges in a bipartite graph

I have to prove that for a bipartite graph G on n vertices the number of edges in $G$ is at most $n^2/4$. I used induction on n. induction hypothesis:Suppose for a bipartite graph with less than ...
1
vote
1answer
208 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 ...
0
votes
1answer
1k views

Hamiltonian Cycle Problem

At the moment I'm trying to prove the statement: $K_n$ is an edge disjoint union of Hamiltonian cycles when $n$ is odd. ($K_n$ is the complete graph with $n$ vertices) So far, I think I've come ...
10
votes
3answers
1k views

Is the empty graph connected?

Is the empty graph always connected ? I've looked through some sources (for example Diestels "Graph theory") and this special case seems to be ommited. What is the general opinion for this case ? As ...
6
votes
2answers
4k views

Prove that the chromatic polynomial of a cycle graph $C_{n}$ equals $(k-1)^{n} + (k-1)(-1)^{n}$

This is a homework question. But I am completely stuck. My only intuition was to go about it inductively from a "greedy algorithm" maybe know as the deletion-contraction algorithm. And to somehow use ...