# Tagged Questions

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.

667 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 ...
932 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 ...
27k 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 ...
7k 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 ...
3k 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 ...
4k 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 ...
265 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 ...
5k 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!
4k 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 ...
14k 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 ...
5k 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 ...
14k 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 ...
420 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. ...
2k 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 ...
462 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 ...
11k 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 ...
35k views

### Proving that the number of vertices of odd degree in any graph G is even

I'm having a bit of a trouble with the below question Given $G$ is an undirected graph, the degree of a vertex $v$, denoted by $\mathrm{deg}(v)$, in graph $G$ is the number of neighbors of $v$. ...
1k 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$ ...
1k views

### If a graph with $n$ vertices and $n$ edges there must a cycle?

How to prove this question? If a graph with $n$ vertices and $n$ edges it must contain a cycle?
379 views

6k 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 ...
2k views

### Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
267 views

### Prove the statement 'World is not flat'

In my graph theory book exercise, I found a problem that: Prove that the World is not flat using Mathematics This picture is used in the exercise, but no idea of applying it. I would have ...
16k 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.
3k 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 ...
8k 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 by ...
2k views

### Automorphisms of the Petersen graph

I am trying to find out the automorphism group of the Petersen graph. My book carries the hint: "Show that the $\tbinom{5}{2}$ pairs from {1, . . . , 5} can be used to label the vertices in such a way ...
1k views

### Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
### prove that a connected graph with $n$ vertices has at least $n-1$ edges
Show that every connected graph with $n$ vertices has at least $n âˆ’ 1$ edges. How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges: a-----b-----c ...
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 ...