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

0
votes
1answer
83 views

Cycle type of induced permutation

Let $m = \binom{n}{2}$ and $S_n, S_m$ be the symmetric groups, $S_n \subset S_m$. Let $\pi \in S_n$ and let $\pi$ have the the cycle type $[λ_1,λ_2,\dots,λ_k]$, $\lambda_1+\lambda_2+ ...
2
votes
1answer
96 views

Graph Theory - Concept checking questions.

Q. Suppose $G=(V,E)$ is a simple undirected graph with no self-loop; moreover, the graph $G$ has $n=|V| ≥ 1$ vertices, $m=|E|$ edges, $k$ connected components, $p$ odd cycles, $q$ even cycles and ...
1
vote
0answers
39 views

Can a planar graph have multiple edges joining 2 vertices?

If they are planar, do the properties $2E \geq 3F$ and $E \leq 3V-6$ remain true? For example, consider 2 vertices joined by 2 non-intersecting edges. Then $E=2, F=2$ and $V=2$ and $2E \not > 3F$. ...
1
vote
1answer
115 views

Given G an Undirected Graph with > 3 Vertices(V). Prove that V Can Always be of 3 Colors Such that at Least 2/3 Edges don't Connect V of Same Color

Let $G$ be an undirected graph with $n>3$ vertices and $m$ edges. $\text{Edges} = \{ (i_{i} < j_{i}), \dots, (i_{m} < j_{m}) \}.$ Prove that we can always color vertices in 3 colors such that ...
1
vote
0answers
50 views

“Let $G$ be a planar graph. Show that every pair of vertex-disjoint odd cycles in $G^c$ is connected by an edge.” Can't figure out why “odd” matters.

If $C_1,C_2$ are vertex-disjoint cycles in $G^c$, of lengths $m,n$ respectively, not connected by an edge, then their complement has a $K_{m,n}$ minor with $m,n\geq 3$, so $G$ contains $K_{3,3}$ as a ...
1
vote
1answer
103 views

Calculate a determinant related to permutation matrix

Let $ M$ be a permutation $n \times n $ matrix and $[\lambda_1,\lambda_2, \ldots,\lambda_n]$ be the cycle type of the corresponding permutation, i.e. $ \lambda_i$ is the number of cycles of the ...
2
votes
2answers
89 views

Minimum number of elements needed from n sets

Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set? For ...
1
vote
1answer
55 views

How to Prove that a 3-regular bridgeless graph has perfect matching? [duplicate]

Proove that a 3-regular bridgeless graph has perfect matching?
4
votes
1answer
719 views

How to show that a self-complementary graph must have $4k$ or $4k+1$ vertices [duplicate]

How do I prove that a self-complementary graph must have $4k$ or $4k+1$ vertices?
2
votes
0answers
47 views

Puzzle - connecting nodes

This might not be the right stack exchange, so if there's a better place to put it please let me know. I have the following problem. Given the following graph, ignoring X, find all possible ...
1
vote
1answer
204 views

3-Colorability Graph Questions

I know that a boolean formula for 3-colorability is : $ \wedge_{i \in Vertices}(\bar{b_{i,1}} \vee \bar{b_{i,2}}) \wedge_{\left(i < j \right)\in Edges} ((b_{i,1} \bigoplus b_{j,1}) \vee (b_{i,2} ...
3
votes
2answers
334 views

List of ways to tell if degree sequence is impossible for a simple graph

I'm trying to make a list of ways to tell if a given degree sequence is impossible. For example $3,1,1$ is not possible because there are only 3 vertices in total so one can't have degree 3. The ...
2
votes
1answer
78 views

Smallest graph possessing a property

I was studying about Almost self-centered graphs. http://link.springer.com/article/10.1007%2Fs10114-011-9628-3 My doubt is what would be the minimum number of vertices for such graphs. My idea: I ...
0
votes
1answer
196 views

Proving that the number of leaves in a Full Binary Tree is greater than number of internal vertices

I was working on my own inductive proof and I need some feedback since I couldn't find a similar proof over Math Exchange. I've got a feeling that this proof is around where it's supposed to be but ...
0
votes
1answer
87 views

Graph isomorphism

The definition for graph isomorphism states that two graphs $G_1 = (V_1,E_1)$, $G_2 = (V_2,E_2)$ are isomorphic if there is an isomorphism $f:V_1\to V_2$ such as each $u$ and $v$ vertex from $V_1$ are ...
0
votes
1answer
220 views

Chromatic number of complement of bipartite graph

What is the chromatic number of the complement of bipartite graph on $n$ vertices? If I have a complete bipartite graph $K_{1,n-1}$, then its complement are two disconnected complete graphs, $K_1$ ...
1
vote
2answers
87 views

Graph Theory Software [duplicate]

I am looking for software to draw graphs with edges and nodes, show colorings, etc. Where can I find such software?
0
votes
3answers
384 views

How to find number of subgraphs of complete bipartite

How many subgraphs does $K_{4,6}$ have? Is the question asking to find all possible combinations of vertices and edges? If yes, the number of subsets of 4 vertices is $2^4$ but then I'm not sure how ...
0
votes
1answer
320 views

Which of the following graphs has an Eulerian circuit?

Which of the following graphs has an Eulerian circuit? a) Any k regular graph where k is an even number b) A complete graph on 90 vertices c) The complement of a cycle on 25 vertices d) None of the ...
4
votes
1answer
117 views

Prove that the Möbius ladder and the toroidal ladder are non-isomorphic graphs.

I just gave this problem on my graph theory final, and I can't wait to see what innovative approaches my students come up with. The two ladders are defined to be the only $3$-regular graphs that can ...
4
votes
1answer
61 views

Get from point A to point B efficiently.

This is a question I thought about while crossing the street. Suppose you're standing at the bottom-left corner of a rectangle. Your goal is moving to the the top-right corner, efficiently, ...
1
vote
1answer
136 views

How do you prove a degree sequence isn't possible?

For example, why is the degree sequence 3,3,1,1 not possible? I said because there are only 4 vertices and if two of them have degree 3 then the other 2 must have degree 2. Is this "proving it"? What ...
3
votes
1answer
556 views

Prove that every dual graph of a planar graph is planar

It seems obvious, but how to prove it properly? I tried Kuratowski, but got stuck at $K_{3,3}$
1
vote
0answers
80 views

maximum weight on a directed graph (weighted)

I have a problem in finding an algorithm for matching of maximum weight on a directed graph (weighted). In particular, I would also need to find all the matching induced by subgraphs of the given ...
1
vote
1answer
69 views

Why is a graph an ordered pair?

From the source of all knowledge a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V Why ...
0
votes
1answer
128 views

Graph with vertex chromatic number greater than edge chromatic number

is it possible to find a graph whose vertex chromatic number = 2010 + edge chromatic number? And how to prove it? Thank for any advice.
1
vote
1answer
82 views

Aplanar covering of $S^1 \vee S^1$?

Can someone provide an aplanar covering of $S^1 \vee S^1$? What if I insist on it being finite degree? (This question is motivated by the diagram in the first chapter of Hatcher's Algebriac Topology, ...
0
votes
2answers
63 views

Necessary and sufficient condition so an edge-weighted complete graph has even weight on all cycles

Let $O\subseteq K_n$ be the subgraph of $K_n$ with odd-weight edges. The problem is to prove that all cycles in $G$ have even weight if and only if $O$ is a spanning complete bipartite subgraph of ...
1
vote
2answers
68 views

Is it possible to draw a graph that has an Euler Cycle but not a Hamilton Path?

Is it possible to draw a graph that has an Euler Cycle but not a Hamilton Path? It seems every Euler cycle I draw has a Hamilton Path.
1
vote
1answer
58 views

Is it possible to draw a graph with a Hamilton Path but not a Euler Cycle?

Is it possible to draw a graph with a Hamilton Path but not a Euler Cycle? It seems that every graph I draw has a Hamilton Path.
2
votes
1answer
56 views

Discrete maths; graph theory on undirected graphs

Let G be an undirected graph of 4 vertices and no loops (i.e. arrows to itself). Which of the following statements are guaranteed to be true? 1) G has at least two vertices of the same degree 2) G ...
0
votes
1answer
80 views

Ergodicity of this Markov Chain

I was recently involved in a debate with a friend over the following graph, and whether it is ergodic or not. In the following diagram, each edge has a strictly positive probability of being travelled ...
0
votes
1answer
47 views

Algorithm to partition a graph under constraints

What would be an algorithm to partition the vertex set of an undirected graph into 2 vertex disjoint subsets such that each vertex has at most $\left\lfloor\frac{d}{2} \right\rfloor$ no of its ...
0
votes
1answer
194 views

Degree distribution of a graph

Given a graph, what is the degree distribution of the same? Is degree distribution the same as a histogram of the degrees? As in, is the degree distribution a plot of the number of nodes that have a ...
1
vote
1answer
68 views

What is the proof that $\sum \limits_{v \in V} deg(v) = 2|E|$?

My textbook gives $\sum \limits_{v \in V} deg(v) = 2|E|$ and has the proof If an edge is not a loop it gets counted twice b/c it's incident with 2 different vertices. If an edge is a loop, by ...
1
vote
1answer
89 views

Edge-disjoint paths in $k$-regular graphs

Is it correct to assume that every $k$-regular graph has at least $k$ edge-disjoint paths for every pair of vertices? If so, how could someone prove it?
0
votes
2answers
63 views

Can two overlapping disconnected graphs contain a Euler Circuit or Path? Hamilton Circuit or Path?

Can two overlapping disconnected graphs contain a Euler Circuit or Path? Hamilton Circuit or Path?
0
votes
1answer
132 views

How to prove this necessary and sufficient condition for tree in graph theory?

Let $0<d_1\leq\ldots\leq d_n$ be integers. Show that there exists a tree with degrees $d_1,\ldots,d_n$ if and only if $d_1+\ldots+d_n=2n-2$.
2
votes
1answer
99 views

Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...
0
votes
1answer
45 views

How to know if $(8,7,7,6,5,5,4,3,3,2,1,1)$ is a Simple Graph w/o using Havel-Hakimi Algorithm

I've used the Havel-Hakimi Algorithm to show this sequence $(8,7,7,6,5,5,4,3,3,2,1,1)$ is simple, but is somewhat time consuming for a test. Is there a way to determine without using algorithms? Or ...
1
vote
1answer
43 views

Vertex coloring proof question

There is a graph $G$ such that if any pair of vertices is removed, then its chromatic number decrease by $2$. Show that $G$ is complete graph.
1
vote
0answers
28 views

Conservativeness on a graph

I'm trying to build a conservative vector field out of something smaller than $\mathbb{R}^2$ to understand how the "conservative" property of differences-of-scalar-fields leads to Green's theorem. (In ...
0
votes
2answers
400 views

traveling salesman with pairs of cities, without return and with given start and end cities

I am looking for the name of the following two problems, and an approach to solve them. Problem#1: given N nodes, find the shortest path starting at a given start node and ending at a given end node, ...
0
votes
3answers
75 views

Find a graph on a torus (tutorial)

Find the $K_{4,4}$ graph on a torus. So, that's my homework. I've even found it in one of my textbooks, but only the solution, not a how-to-do-it method. I would really appreciate a step-by-step ...
1
vote
0answers
84 views

How many London underground stations you can visit without passing through the same station twice?

If you can start anywhere and only travel on the lines shown in the official map (http://www.tfl.gov.uk/assets/downloads/standard-tube-map.pdf) (including overground, DLR, Emirates Air Line and ...
3
votes
3answers
144 views

Is there a method for systematically enumerating sets of collinear nodes in a graph?

This question arises directly from the discussion in this MSE question which I'd posted a few days back: Counting the number of polygons in a figure. In that question, I'm currently trying to find a ...
1
vote
2answers
104 views

Finding number of paths between vertices in a graph

According to my book, this is how it's done: What exactly does $A^r$ represent? Here is an example they did and I have no clue where all those 8s and 0s came from..
3
votes
4answers
242 views

Chromatic Polynomial of Ladder Graph

Hey guys I am trying to understand the formula for the chromatic polynomial of a ladder graph. $$k(k-1)(k^2-3k+3)^{n-1}$$ Can you guys help me understand how we get to this?
2
votes
1answer
73 views

Minimal time to ride all ski slopes

Suppose we want to know what the minimum time is to ride all ski slopes on a mountain. We know the time it takes to ride a slope, and we know the time it takes to take a ski lift to get from one ...
0
votes
1answer
29 views

Defining a graph as G=(V,E) — how to interpret the notation?

I am looking at the following problem: Define $V=\{0,1,2,3,4,5\}$. Define a graph $G=(V,E)$ by letting the edges be: $$ E =\{(a,b):a-b^2 \le 1 \lor b-a^2 \le 1\}$$ I understand that 'V' stands for ...