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
2answers
18 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
13 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 ...
3
votes
2answers
33 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
0answers
27 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?
9
votes
2answers
569 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
34 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
17 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
23 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
25 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
32 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
24 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
25 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
56 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
54 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
212 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 [on hold]

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
14 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
26 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
47 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 ...
0
votes
1answer
26 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 ...
0
votes
0answers
11 views

Network Coding multicast r symbols simultaneously. Physically How?

I understand how network coding works but physically how r symbols can be multicast to all destinations from one source? For example in following butterfly network, there are two symbols which can be ...
-6
votes
0answers
22 views

If A is the adjacency matrix for a graph $G$, what is the number of paths (both simple and non-simple) of length $k$ from node $i$ to $j$ in $G$? [closed]

If A is the adjacency matrix for a graph $G$, what is the number of paths of length $k$ from node $i$ to $j$ in $G$? Note that this answer should include simple paths (no cycles allowed) and ...
1
vote
1answer
51 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
21 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 $≥ ...
8
votes
0answers
44 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
17 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
47 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 ...
-2
votes
1answer
31 views

What is the chromatic number of $K_n$, $P_n$, $C_n$, trees, and the Petersen graph? [closed]

Find $\chi(K_n)$, $\chi(P_n)$, $\chi(C_n)$, and $\chi(\text{Petersen graph})$. The other part is: Prove that $\chi(T)=2$ for any tree. Thank you so much. Please provide a detailed proof.
-1
votes
1answer
23 views

graph theory proof for square division into rectangle [closed]

a square was divided into 1000 triangles with equal areas. Then the same square was divided into 1000 rectangles with equal areas. Prove that there exists 1000 points inside the square such that every ...
1
vote
1answer
20 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
59 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 ...
-4
votes
1answer
44 views

Graph Theory Chessboard problem [closed]

From the $8 \times 8$ chessboard, $7$ cells were cut out. Prove that you can put $8$ rooks on this board so that none of them can capture another rook. Thank you.
0
votes
0answers
29 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
35 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
21 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
22 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 ...