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
0answers
9 views

Find longest route through graph with restrictions

Q.4 from http://www.iarcs.org.in/inoi/2015/zio2015/zio2015-question-paper.pdf All flights must originate at airport 0 and end at airport 2. The types of flight taken during the sequence must match ...
0
votes
1answer
17 views

Proof that in a Simple Graph with number of nodes $\geq 2$ there is at least one node $v$ can be removed and keeping the Graph connected$

Proof that in any Simple Graph $G$ with number of nodes $\geq 2$ there is at least one node $v$ can be removed with its all edges, and keeping the Graph $G$ connected ? From my point of view I can ...
1
vote
0answers
17 views

What is the formalism for a map that returns the adjacent vertex positions of a given adjacency matrix?

How do I formally denote a map that returns the adjacent vertex positions of a given adjacency matrix? Example: V = undirected adjacency matrix $$ V = \left[ \begin{matrix} v_{1,1} & v_{1,2} ...
0
votes
0answers
44 views

Number of graphs with 5 vertices

Let $v_i$ where $i=1,2,3,4,5$ be vertices of a graph. Each vertex makes only one directed edge to any other vertex. For instance $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ and $v_1 \to v_3 \to v_4 ...
3
votes
0answers
46 views

How can I calculate the formula of this fractal-like structure?

I did the following fractal-like structure manually, and I was trying to convert it to a formula (or an algorithm including formulas) to compute some parts of the drawing, but I get lost due to the ...
2
votes
1answer
24 views

Let G be a simple graph with n vertices and m edges. Prove the following holds!!

Let G be a simple graph with n vertices and m edges. Prove the following holds using the Handshake Theorem: $$\frac{m}{\Delta} \leq \frac{n}{2} \leq \frac{m}{\delta}$$ where: $\Delta$ is the maximum ...
1
vote
0answers
42 views

How to give a rigorous proof of a fact about convex polygon?

I claim that there exists universal constants $0<\delta_1(m), \delta_2(m)<1$ such that for any convex polygon $P$ in $\mathbb{R}^n$ with $m$ faces, \begin{equation} \frac{\mathcal{H}^{n-1}(\{x ...
2
votes
1answer
28 views

Counterexample to a variation on “The politician theorem”.

The following is a theorem in graph theory that has a nice 'real world' interpretation: Suppose $G$ is a finite simple graph in which any two vertices have precisely one common neighbour. Then ...
0
votes
0answers
6 views

graph theory k -coloring proofs, specific problem using countries and neighbors

prove that if any country has at least 5 neighbors, then there are two neighboring countries such that there are not more than 9 other countries adjacent to at least one of these two, each country is ...
0
votes
0answers
13 views

graph theory proof for chromatic number k and length of a path

Prove that if the chromatic number of G = k, then for every k-coloring of G, there is a path of length k-1 in G with different colors of vertices. Thanks much
1
vote
0answers
18 views

Graph Theory, West, 2nd ed, Exercise 1.2.14

The claim to prove, or disprove is as follows: The union of the edge sets of distinct $u,v$-paths must contain a cycle. The proposed solution is the following: Proof (extremality): Let $P$ ...
0
votes
1answer
17 views

Is every bijective pseudograph homomorphism a pseudograph isomorphism?

The term pseudograph describes a graph that may have parallel edges and loops. Formally this is a triple $G = (V,E,\delta)$ with $V,E$ sets and a map $\delta \colon E \to (V \times V)/\sim$, where ...
4
votes
1answer
31 views

Proposition $1.3$ in Bondy & Murty's Graph Theory.

Let $G[X,Y]$ be a bipartite graph, with no isolated vertices, and $d(x) \ge d(y)$, $\forall$ $xy \in E$ (where $E$ denotes the set of edges in $G$). Then: $|X| \le |Y|$, with equality iff $d(x) = ...
0
votes
0answers
16 views

Standard notation for the set of children of a node in a rooted tree

In graph theory, given a rooted tree $T$ and a node $a \in V(T)$, is there a standard way to refer to the set of all children of $a$? I have seen $CHILDREN_T(a)$ being used, but this seem quite clumsy ...
2
votes
1answer
45 views

Friendship theorem: need help with part of proof.

Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a ...
0
votes
0answers
18 views

Determine $ex(n,P_k)$ for each pair of n and k

I have to find the maximum number of edges in $P_k$ free graph where $P_k$ is path of length $k$. I know the result that a graph on $n$ vertices with no path of length $k$ has edges$\ \le ...
1
vote
0answers
19 views

Maximum number of edges in a subgraph of hypercube

Let $H_n$ is an $n$-dimensional hypercube, $|V(H_n)|=2^n, |E(H_n)|=n2^{n-1}$. Let $M\subset V(H_n), |M|=2^k, 1\le k<n$, and $G_M$ is a subgraph of $H_n$ induced by $M$, $V(G_M)=2^k$. Prove that ...
0
votes
2answers
24 views

$K_n$ as an union of bipartite graphs

Theorem: The complete graph $K_n$ can be expressed as the union of $k$ bipartite graphs if and only if $n \leq 2^k.$ I would appreciate a pedagogical explanation of the theorem. Graph Theory by West ...
1
vote
1answer
16 views

Showing an outerplaner graph has less than $2n-3$ edges

An outerplanar graph is a connected plane graph that can be drawn in such a way that all it's vertices are on the outer face. I want to show that for every $G$ outerplaner graph with $n$ vertices and ...
4
votes
2answers
46 views

(A question regarding:) the graph associated with an open cover of a topological space.

Let $X$ denote a topological space and suppose that $\mathcal{O}$ is an open cover of $X$. Assume $\emptyset \notin \mathcal{O}.$ (Thanks Niels!) Now make $\mathcal{O}$ into an (undirected) graph as ...
2
votes
1answer
46 views

Homology of a graph.

Let $\Gamma$ be a graph with $V$ vertices and $E$ edges. If we orient the edges, we can form the incidence matrix of the graph. This is a $V\times E$ matrix whose $(i j)$ entry is $+1$ if the edge ...
0
votes
0answers
18 views

It is possible to have multiple values in one graph node

Look at the graph: I have this graph and i want to return all possible groups of the graph. Each group is a node, or all the nodes directly below that node. So we can have this type of groups: ...
-3
votes
1answer
25 views

Determine the number of graphs with v vertices [on hold]

How can one determine the number of graphs with a certain number of vertices?
10
votes
2answers
575 views

In a graph, can an edge be in less than 2 faces?

In the proof that for every conective plane graph on $n$ vertices and $m$ edges $m\leq 3(n-2)$ I encountered the statement: $\Sigma_{f\in F} f\leq 2m$, and the explanation was that every edge is in at ...
2
votes
3answers
23 views

Picking edges from a connected graph so that any vertex is incident with an odd number of those edges

Suppose you are given a connected graph G having an even number of vertices. Show that you can select a set $E$ of edges from this graph so that any vertex in G is incident with exactly an odd ...
1
vote
1answer
30 views

Graph and tree computation

A graph is given with set of nodes $[x_1,x_2,x_3,\ldots,x_6]$ and with set of edges: $$\{[x_1,x_2], [x_1,x_3], [x_1,x_4], [x_1,x_5], [x_1,x_6], [x_2,x_3], [x_2,x_6], [x_3,x_4], [x_4,x_5], ...
-1
votes
2answers
23 views

What is the adjacency matrix and number of paths of length $4$ between vertex $2$ and vertex $5$ in the null graph on $\{1,2,3,4,5\}$? [on hold]

Given the following graph 1) Compute adjacency matrix 2) Compute the number of paths of length 4 from knot Nr.2 to knot Nr.5 Can anyone provide a solution how to do it?
6
votes
1answer
36 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 ...
0
votes
1answer
18 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
28 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
26 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
36 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 ...
-1
votes
0answers
26 views

Number of simple, connected graphs with K edges and N distinctly labelled vertices [on hold]

Ok. I'm aware of this question and answer, but it's over my head. I've written a recursive function that I thought would do the job, but it doesn't, apparently. Could someone explain to me why it's ...
-2
votes
0answers
26 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
15 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
24 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
59 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 ...
2
votes
1answer
57 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
215 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
10 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 ...
-2
votes
0answers
21 views

Prove that for any polyhedron [closed]

Prove that for any polyhedron there are two faces with the same number of vertices.
-1
votes
1answer
36 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
27 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
28 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 ...
7
votes
0answers
50 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
37 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
14 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 ...