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

1
vote
0answers
27 views

Prove that if $\chi(G) > k \wedge |\{\operatorname{ad}(H): \text{$H$ is an induced subgraph of $G$}\}|$ then $G$ has a $k-regular$ induced subgraph? [duplicate]

I have found an interesting exercise in my introduction to graphs workbook: Let $\operatorname{ad}(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $\operatorname{mad}(G) = ...
0
votes
1answer
92 views

Checking if a graph is fully connected

I have an adjacency matrix of an undirected graph (the main diagonal contains 0's) and I need an algorithm in psuedocode that will check whether the graph is fully connected (i.e. that one can walk ...
0
votes
1answer
52 views

A Combinatorial problem , matrix

I am trying to solve the following problem : Let A be a square matrix whose entries are zeroes and ones. It is allowed to put minus ones instead of ones . Prove that this can be done in such a way ...
1
vote
2answers
200 views

Prove that a complete hypercube graph is connected. i.e. there is a path between every pair of vertices.

Prove that a HyperCube graph is connected. i.e. there is a path between every pair of vertices. I was able to find proof for bipartite, but I'm curious how hypercube is related.
0
votes
2answers
88 views

Find a sequence which has an even number of odd terms, and yet the sequence is not a graph score.

Construct an example of a sequence of length n in which each term is some of the numbers 1, 2, . . . , n − 1 and which has an even number of odd terms, and yet the sequence is not a graph score. ...
2
votes
1answer
273 views

Proving Cographic matroid is indeed a matroid

Given a connected graph $G=(V,E)$ let us define $M(G)=(E,I)$ where $I=\{E'\subseteq E | (V,E\backslash E') \text{ is connected}\}$. When proving $M(G)$ is a Matroid we must show: if $A,B\in I$ ...
2
votes
2answers
167 views

Checkers on a Chessboard

Given 2k pieces on a k by k chessboard, prove that there is always a sequence of pieces $K_1, K_2 \ldots K_{2n}$ such that $K_1$ and $K_2$ are in the same row, $K_2$ and $K_3$ are in the same column, ...
1
vote
2answers
829 views

Rank of adjacency matrix vs rank of graph Laplacian

What is the relation between rank of the adjacency matrix of a graph and rank of the corresponding graph Laplacian matrix?
1
vote
2answers
247 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
76 views

Existance of Hamiltonian cycle in the connected graph.

I know the fact, that if a graph is connected and each of its vertices has a degree of $2$, then graph is a cycle graph and it has a Hamiltonian path. From that I easily conclude, that, if graph with ...
1
vote
1answer
778 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
0answers
30 views

Edge versus vertex assignment in graphs

Consider a graph $G = (V,E)$. Let $x \in \{-1,1\}^V$ be a label assignment to vertices of the graph and $z \in \{-1,1\}^E$ be a label assignment to edges of the graph. We say that $z$ is compatible ...
1
vote
0answers
42 views

fitness cost calculation finding the weighted sum

I am having a little bit of trouble making a weighted sum calculation for subpaths(Where subpath is the path between two cities e.g. A->B) in a travelling salesman problem. Basically I have 3 ...
5
votes
1answer
534 views

Ruler and compass construction of the unit-distance petersen graph embedding

The Petersen graph is a unit distance graph, and this embedding is shown below, where each edge of the graph is one unit in length. Is there a ruler and compass construction for this embedding? If ...
2
votes
0answers
127 views

Lattice theory in mathematics and physics

I have undertaken a project examining lattice model and trying to construct algorithm that could work on all lattice (in physical sense, or crystal structure). I notice there is a branch in ...
2
votes
1answer
728 views

A graph with a degree sequence 0,1,2,3,4 [closed]

Please help me to prove whether or not a there exists a graph with the degree sequence 0,1,2,3,4. I do not know the formal way of writing the proof hence any advises and proofs will be much ...
0
votes
0answers
32 views

Calculate self-avoiding-filling-polygons

Definition of self-avoiding-filling-polygon In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. ...
1
vote
1answer
88 views

Number of branchings on {1,…,n}

A branching is a digraph G, such that the indegree of every vertex is at most 1 and the underlying undirected Graph has no cycles. Show that there are $(n+1)^{n-1}$ branchings on the set of vertices ...
1
vote
1answer
88 views

Find self-avoiding-filling-polygon represented by system of linear equations

In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. I want to find self-avoiding-filling-polygon from my graph ...
2
votes
2answers
1k views

Graph Theory Complements

Let G be a simple graph with n vertices. What is the relation between the number of edges of G and the number of edges of the complement G'? In the example below, I noticed that by adding the ...
1
vote
1answer
335 views

Dilworth's Theorem is equivalent to Hall's

I have been told that Dilworth's Theorem implies Hall's Theorem. I don't seem to be able to show this implication, especially because I haven't done any graph theory in a while! Any help? If possible, ...
0
votes
1answer
192 views

If $G$ is simple with diameter two and maximum degree $|V(G)| - 2$, then $|E(G)| \geq 2|V(G)| - 4$

This is my try: Because the diameter of $G$ is two and have maximum degree the number of vertex: $|V(G)| - 2$, where $|V(G)|$ is the number of vertex, then the grade for any vertex in $G$ is greater ...
1
vote
1answer
49 views

Graph Ramsey Theory for Multiple Copies of Graphs

I had the following question from Graph Ramsey theory. Show that if $m \geq 2$, then $$ R((m+1)K _{3},K _{3})\geq R(mK _{3},K _{3}) + 3. $$ Thanks.
0
votes
1answer
37 views

Basic question about claw-free graphs and independant sets

The wiki page for claw free graph says if I is an independant set in claw free graph then any vertex v has at most 2 neighbors in I. It says if it has more you get a claw but if it had 4 neighbors in ...
1
vote
0answers
173 views

relationship between kruskal algorithm and TSP

Question $8$: Is the TSP tour obtained in Question 7 optimal? For question $6$, I got total weight is 60. Edges are $1-2, 2-4, 3-4, 3-9, 5-6, 6-7, 7-8, 8-9$ Question $7$: We need to add the edge ...
1
vote
1answer
111 views

algorithms directed graph and its sources

Give a linear-time algorithm that takes as input a directed graph in adjacency list format, and outputs all of its sources. i know that a source in a directed graph is a node that has no edges going ...
-1
votes
1answer
90 views

Lp optimal solution question

i have a general question. if there is a general LP problem $c^Tx$ s.t $A\cdot x \le b$, and $x \ge 0$ and assuming that the components of $c$ are non-zero entries then how can I prove that when $x$ ...
0
votes
2answers
72 views

Undirected Graph Bipartite

I am unsure how to approach this problem: Prove that an undirected graph is bipartite if and only if there are no edges between nodes at the same level in its BFS tree. (An undirected graph is ...
1
vote
1answer
35 views

Does the Prim algorith always create the same tree despite the starting node?

Does the Prim algorith always create the same tree despite the starting node? PD: sorry for my english.
0
votes
1answer
103 views

Are these equivalent representations (labelled graph and adjacency matrix)?

This is an example from Wikipedia's page on adjacency matrices, which from the site's format seems to be suggesting equivalence between the simple diagram below, left, and the abstractly represented ...
4
votes
0answers
125 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
0
votes
1answer
48 views

Exact distance geometry problem proof

How can one prove that the degree of each node in a distance graph must be at least four in order to obtain a unique solution to an exact distance geometry problem with sparse distance data? The ...
0
votes
1answer
79 views

Theorem on friends and strangers: 2 triangles

According to this problem: http://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers Is it possible to have BOTH 3 strangers and 3 friends at the same time on complete graph of 6 vertices? That ...
0
votes
1answer
80 views

Clarification on proof by contradiction in a directed graph

Let's say that I have a finite directed graph. Also assume that every vertex in the graph has only one unique closest neighbor. How can I prove that the maximum length of any cycle in this graph is 2? ...
2
votes
1answer
77 views

There does not exist a bipartite cubic planar graph on $10$ vertices :

I want to prove : There does not exist a bipartite cubic planar graph on $10$ vertices. I saw same question registered at this site, but I couldn't understand all of solution. According to Euler's ...
2
votes
1answer
64 views

A bicolored plane graph contains a vertex with low oscillation

$G$ is a planar graph, and all edges of $G$ are colored white or black. Prove that in any drawing of $G$ there exists a vertex $v$ such that going around the edges incident with $v$ in the clockwise ...
2
votes
2answers
73 views

Creating Visualisations of Random Graphs

I've got some code in C that produces a whole load of random geometric graphs and finds the proportion that percolate in order to estimate the full connection probability. However I need to produce ...
1
vote
1answer
60 views

How can knowing the *number* of strongly connected components of a directed graph help us detect its cycles?

I understand that when you know the strongly connected componentes of a directed graph, it can help us detect the cycles of the graph, as all the cycles will occur in each SCC. But how can just ...
2
votes
1answer
125 views

Containment in sets

I have a collection of items, each of which belongs in exactly three sets. Each set contains exactly $m$ items. Given numbers $x_2, x_3$, how can I choose $k$ sets such that $x_2$ of the items are ...
2
votes
0answers
137 views

Crystal structure, lattice, periodic graph and coloring

I am working across mathematics, physics and engineering. And I am looking for whether there exists already formally established knowledge in the field. Given a periodic graph (actually a physical ...
0
votes
0answers
101 views

Maximum matching in a non-bipartite graph

The problem is the following; I would like to reach maximum matching in a 2-connected graph, but not in an ordinary way - both of the groups of vertices that we get after the matching should remain ...
1
vote
1answer
189 views

Cayley graphs of Abelian groups quasi-isometrically embeddable in R^d

Are all Cayley graphs of ${\mathbb Z}^d$ quasi-isometrically embeddable in ${\mathbb R}^d$? Or, else, do they all have the same growth exponent? Is it the same true for all finitely-generated Abelian ...
0
votes
1answer
52 views

Can this famous theorem extended to the weighted undirected graphs?

There is well-known bound on the largest eigenvalue of graphs that says $$\sqrt{d_{max}}\leq \lambda_{max}$$. Is it also true for weighted graphs? (Where as usual, the degree of a vertex in a weighted ...
2
votes
0answers
186 views

Stable Marriage Problem

I would just like clarification for the following problem: Suppose $M_1$ and $M_2$ are two stable matchings between n men and n women, and we allow each woman to choose between the man she is paired ...
2
votes
0answers
148 views

Probability of having a path of a given length in a random graph

Suppose $G=\langle V,E \rangle$ is a directed graph consisting of $n\in \mathbb{N}$ vertices. Vertex $v_i \in V$ has an edge to vertex $v_j \in V$ with a probability of $P(i, j) = f(|i-j|)$ where $f$ ...
0
votes
0answers
57 views

Bound on product of degrees

Is there any more or less sharp bound on the product of the out-degrees of vertices in a directed graph (except for the ones with no leaving edges)? The graph may have multiple edges between two ...
1
vote
1answer
123 views

Prove that if a graph contains a bridge, it is not Hamiltonian. Can it contain an Hamiltonian path?

A bridge in a connected graph G is an edge whose deletion disconnects the graph. (Only the edge is deleted | not the vertices.) Prove that if a graph contains a bridge, it is not Hamiltonian. Can it ...
0
votes
1answer
41 views

Subgraphs and homomorphisms

Let $G_{sub}$ be a subgraph of $G$. When can one expect a homomorphism from $G$ to $G_{sub}$? Are there any criteria - algebraic or spectral? Any literature sources on this problem will be helpful. ...
4
votes
2answers
125 views

Bound on graph edges

I need some help with the following problem. Suppose I have a graph $G$ of $n$ elements such that each edge $e$ missing from it, is contained in a copy of $K_s$ (complete graph os $s$ vertices) in ...
1
vote
5answers
179 views

When is round-robin scheduling possible and with in minimal time?

Suppose that you have six teams $x_0, x_1, x_2, x_3, x_4, x_5$. Can you schedule round-robin games between them so that if one game is played each day, the series of games can be completed in five ...