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

6
votes
1answer
39 views

$2$-coloring of graph has large connected subgraph with one color

Given a graph $G$ with $n$ vertices. Let $k$ denote the minimum degree among the vertices. Suppose that $k\geq 3n/4$. We color the edges of $G$ in $2$ colors. Prove that there is a connected subgraph ...
1
vote
1answer
30 views

Definition of Reducible matrix and relation with not strongly connected digraph

I connot quite understand the definition of reducible matrix here. We know $A_{n\times n}$ is reducible, when there exists a permutation matrix $\textbf{P}$ such that: $$P^TAP=\begin{bmatrix}X ...
0
votes
0answers
29 views

Degree-Constrained Shortest Path Problem

The following is my problem: Given an undirected graph G(V,E) with cost c(e) associated with every edge e∈E such that c(e)>0 and a vector d=(dv : v∈V) which denotes the maximum degree on each vertex ...
0
votes
0answers
28 views

Graph, Relation $xRy \Leftrightarrow$ There is a path between $x$ and $y$ - symmetry

I have the relation $xRy$ is equivalent to "There is a path between $x$ and $y$" If I now want to check symmetry, $xRy$ is equivalent to $yRx$, I read that this is true. I thought this is only the ...
0
votes
0answers
52 views

Minimum spanning tree for a weighted square grid

I have a particular grid with weighted edges connecting each vertex: From this I'm looking for an easy method to obtain a Minimum Spanning Tree. I can easily check columns or rows and remove all ...
0
votes
1answer
42 views

K or P Colorable

For any p > 1 find a p-chromatic graph such that all its subgraphs (except itself) are (p − 1)−colorable. Is there any good example for this exercise? I need feedback.
2
votes
1answer
18 views

Reproducing a graph using an incidence matrix

I am very new to graph theory. In fact, I've only begun studying the subject three days ago. So please have mercy if this is a meaningless question! It occurred to me while studying graph ...
0
votes
1answer
28 views

Diameter of a graph?

How do you solve this question? The diameter of the graph $C_m$ $\times$ $C_n$ is? Also what does $C_m$ $\times$ $P_n$ mean? (Taking $m \geq 3, n\geq 3$)
3
votes
1answer
72 views

Another Evaluation of the Ramsey number $\mathcal{R}(3,3,3)$

The problem Show that $\mathcal{R}(3,3,3)=17$ The story behind the problem and some notation It was first proven by Greenwood and Gleason in 1955 in their paper Combinatorial relations and ...
3
votes
1answer
66 views

Graph Theory text for social scientist.

I am a graduate student in Economics. I have a decent grounding in maths, but I've never studied graph theory or combinatorics. I need to study graph theory in order to analyse production networks. ...
4
votes
1answer
227 views

Prove the connected components are uncountably many

Let $G$ a graph with vertices all the points in $\mathbb{R}^2$. An edge exists if and only if the distance between two points is a rational number. Prove that the connected components are ...
0
votes
0answers
16 views

Extract and search an unweighted multigraph from an undirected weighted graph?

I have an undirected weighted graph G(V,E) where the nodes are bus stops and the edges are the distances between the stops. I've implemented a basic Dijkstra to search the shortest path (s, t) which ...
-1
votes
1answer
43 views

the sum of numbers at any row and at any column of this matrix is exactly 1.

All entries of an n × n matrix are non-negative. It is known that the sum of numbers at any row and at any column of this matrix is exactly 1. Prove that you can choose n positive entries such that ...
0
votes
1answer
15 views

Name of a graph that shows various strengths

I am looking for the name of a graph used to show various strengths. It is a polygon and may look like this: _ | | | | | * | _ Where the ...
1
vote
1answer
36 views

Lower bound for the size of a maximal matching in a general graph

Let $G=(V,E)$ be a graph, let $M\subseteq E(G)$ be a maximal matching, and let $M^\star\subseteq E(G)$ be a maximum matching. Prove that $|M|\ge |M^\star|/2$. Any hints on how to prove this?
1
vote
2answers
31 views

Path and cycle length proof

How can we prove this proposition : Every graph G contains a path of length $ \delta(G)$ and a cycle of length at least $ \delta(G) + 1$, provided that $\delta(G) \geq 2 $. ($ \delta(G)$ is the ...
9
votes
1answer
81 views

Dominating a Four Dimensional Chessboard with Rooks

There is a family of chess problems where you try to dominate a board with as few copies of a given piece as possible. The chessboard is dominated if every square either contains a piece, or is ...
2
votes
1answer
26 views

Graph Theory-Eulerian Path?

In a certain country, $40$ roads lead out of each city. When all roads are open, it is possible to travel from any city to any other. Each road leads from one city to another; there are no dead end ...
1
vote
1answer
35 views

help with graph theory question

Let $A_1A_2A_3A_4$ be a square, and let $A_5,A_6,A_7,\ldots,A_{34}$ be distinct points inside the square. Non-intersecting segments $\overline{A_iA_j}$ are drawn for various pairs $(i,j)$ with $1\le ...
0
votes
1answer
39 views

sitting around a table- graph theory?

$50$ mathematicians attend a conference at which each knows $25$ other attendees. Show that you can select $4$ of them who can then be seated at a round table, such that each person at the table knows ...
2
votes
0answers
15 views

Graph Entropy - A Tractable Measure to Measure Distinguishability of Neighbourhoods

Given a labelled directed graph G, I am interested in a measurement of G that captures how distinguishable arbitrary connected sub graphs of G are. Labels may repeat and as such two or more different ...
0
votes
1answer
29 views

Chromatic number of a hypercube

What is the chromatic number $\chi(Q_4)$ of a four-dimensional cube. I know that all Hypercubes $Q_d$ are bipartite, so then this would yield $\chi(Q_4) = 2$, because every bipartite graph has ...
1
vote
1answer
54 views

Count the paths in a graph

For a given graph $G(V,E)$ $V = \{ (x,y) | x = \{0,1, ... , m\}, y = \{0,1, ... , n\} \}$ $E = \{ \{(x,y), (u,v)\} | (x=u \text{ and } |y-v|) = 1 \text{ or } (|x-u| = 1 \text{ and } y=v) \}$ How to ...
0
votes
1answer
26 views

Proof If a tree is not trivial, then there are at least two pendant vertices?

I have the following Proof but could not understand it Proof. If a tree has $n(≥ 2)$ vertices, then the sum of the degrees is $2(n − 1)$. If every vertex has a $degree ≥ 2$, then the sum will be $≥ ...
9
votes
0answers
58 views

What can we say about the graph when many eigenvalues of the Laplacian are equal to 1?

The Laplacian of the graph has all the eigenvalues real and non-negative, the smallest being 0. I have a graph where the second smallest eigenvalue (the so called algebraic connectivity) is equal to ...
-1
votes
1answer
30 views

Perfect matching and maximum matching

In a graph where a perfect matching is possible, is that perfect matching also always the maximum matching?
3
votes
0answers
48 views

What is the diameter of the Cayley graph of $S_n$ w.r.t the generator $\{(12),(23),…,(n−1n)\}$?

Given a symmetric group $S_n $ and the generator set : $S = \{(12),(23), . . . ,(n − 1 n) \}$ is there any closed form expression for the diameter of the Cayley graph generated by this set of ...
1
vote
1answer
23 views

Exlamation about a claim of an existing such cycle in a simple Graph

Suppose the following situation: this is found at (Let G be a graph of minimum degree k > 1. Show that G has a cycle of length at least k+1) Let $P=v_0v_1 \dots v_l$ be a longest path in $G$. ...
2
votes
1answer
65 views

graph theory matrix

all entries of an $n \times n$ matrix are non-negative. It is known that the sum of numbers at any row and at any column of this matrix is exactly 1. Prove that you can choose n positive entries such ...
0
votes
0answers
33 views

Looking to get a handle on SSCG(3) (which is much, much larger than TREE(3))

TREE numbers grow rapidly: TREE(1) = 1, TREE(2) = 3, and a lower bound for TREE(3) is A(A(...A(1)...)), where the number of As is A(187196) and A(n) is a version of Ackerman's function. That's ...
1
vote
0answers
45 views

Deriving deletion-contraction formula from Subgraph Expansion of Chromatic Polynomial

Given a graph $G=(V,E)$, the chromatic polynomial $P(G,q)$ counts the number of $q$-colorings of a graph $G$. It satisfies the deletion-contraction formula: \begin{equation*} P(G,q) = P(G-e, q) - ...
1
vote
1answer
22 views

Complexity of finding M nodes in a graph to maximize the pairwise minimum distance between nodes

I want to know the complexity of finding a set of M nodes, $\{U_1,\dots,U_M\}$, in a given graph $G$, to maximize $d(U_i,U_j)$ over all pairs $i\neq j$, where $d(\cdot,\cdot)$ is the length of the ...
1
vote
1answer
25 views

combinations of graphs with 2 vertices

I am reading graph theroy. Here author mentions that the number of possible digraphs is truly huge. Each of the $V^2$ possible directed edges (including self-loops) could be present or not, so the ...
0
votes
1answer
31 views

Relation between edge expansion of graph and sparsity

I was going through the lectures of Graph Partitioning and Expanders - Stanford Online. In lecture 1, near the end of page 5, I came across this inequality for regular graphs: $$\phi(S) \leq h(S) \leq ...
2
votes
0answers
21 views

Using Erdős–Szekeres theorem for graph with 50 vertices

Let $G$ be a graph with $50$ vertices such that for every $4$ vertices there are $2$ that have no edge between them (independent). I want to prove that $G$ has a group of $5$ independent vertices.My ...
1
vote
1answer
37 views

proof that a cycle space is a subspace

I'm looking at the following proof that the cycle space of a graph is indeed a subspace, which I don't believe to be correct. proof: It suffices to prove that $\mathcal{C}$ is closed under $+$ ...
0
votes
1answer
41 views

maximal planar bipartite graphs

I know that a maximal planar graph is a graph in which no more segments can be added to connect more vertices because then it won't be planar, but I trying to define what a maximal planar bipartite ...
0
votes
0answers
23 views

List of graph data points, need accurate calculation/estimate formula for excel

So I'm working on a small project that will use a calculation in excel, I'm nearly there and the only piece missing is being able to accurately estimate a data point from the following set of data ...
-3
votes
1answer
39 views

Turan graph maximizes the minimal vertex degree

Prove that for every graph $G$ with $n$ vertices and $tr(n)$ edges, the following inequality holds: $$\delta(G) \le \delta(T_r(n))$$ where $T_r(n)$ stands for Turan's graph and $tr(n)$ for its ...
1
vote
1answer
62 views

If $G$ is simple and $deg^+(v)\geq k \geq 1 \space \forall \space v \in V$ there is a simple cycle of at least size $k+1$

I have the following proof but it is tough could someone help me to understand it, Proof: Start at an arbitrary node $v$ and mark it, and so on until you have marked all nodes in the series then a ...
0
votes
2answers
53 views

Proof that if all vertices have degree at least two then G contains a cycle

Here is the proof, but please correct me if wrong : We assume $G$ is simple and let $P$ be the longest path $=v_0v_1v_2\ldots v_{a-1}v_a$. As it is given that the degree of $v_a$ is even ,then $v_a$ ...
0
votes
1answer
42 views

What is Graph Isomorphism and Graph Invariant?

While I was reading Reinhard Diestel text on graphs, I came across this paragraph. Let G = (V, E) and G' = (V' , E' ) be two graphs. We call G and G' isomorphic,and write G $\simeq $ G' , if ...
5
votes
2answers
109 views

Domino Trains Questions

A train is an end-to-end arrangement of dominoes such that the adjoining halves of neighboring dominoes have the same number of dots. A "double-$n$'' domino set has one of each possible domino using ...
3
votes
1answer
46 views

cycle space in graph theory

I read the following definition of the cycle space in a set of notes. Definition (Cycle space): Let $G=(V,E)$ . The cycle space of $G$ is an element of $2^{E}$ denoted $\mathcal{C}$ and is the ...
4
votes
1answer
39 views

Graph vertex set with a certain property

Let $G$ be a graph and let $V$ be a set of vertices with the following property: If a vertex $v$ is connected to every $u\in V$, then $v$ has to be in $V$. Does such $V$ have a (standard) name? Note ...
3
votes
1answer
28 views

Every other vertex shares $5$ neighbors with fixed vertex

An undirected graph has $30$ vertices; one of them is $v$. Each vertex $w\neq v$ shares exactly $5$ neighbors with $v$. Is it true that some vertex must have odd degree? We could try counting the ...
1
vote
2answers
71 views

Given a directed graph, give an adjacency list representation of the graph that leads BFS to find the following spanning tree

Given a directed graph: give an adjacency list representation of the graph that leads Breadth first search to find the spanning tree in the left below. And give an adjacency list representation ...
1
vote
3answers
46 views

When is a graph balanced bipartite?

I have a quick question: is there any sufficient condition (theorem, lemma, proposition,...) to show that a graph (vertices do not have the same degree) is balanced bipartite?
0
votes
1answer
86 views

Prove that a tree in which every vertex has degree at most 2 is a simple path

Prove that a tree in which every vertex has degree at most 2 is a simple path. More precisely: Let $G = (V,E)$ be an undirected tree, with $|V| = n \geq 1$ and assume that every vertex has degree ...
2
votes
1answer
47 views

Minimum cost edge, Minimum Spanning Tree — Graph

Please could I ask for some help with this exam past paper question: A connected graph G has five vertices and has eight edges with lengths 8, 10, 10, 11, 13, 17, 17 and 18. (a) Find the minimum ...