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
7 views

Counting simple, connected, labeled graphs with N vertices and K edges

Given the number of vertices $n$ and the number of edges $k$, I need to calculate the number of possible non-isomorphic, simple, connected, labelled graphs. My question is very similar to this one. ...
0
votes
0answers
8 views

isoperimetric inequalities in permutohedron

Consider the graph whose vertices are all n! permutations of numbers 1..n and there is an edge between two vertices iff we can get from one to another by an adjacent transposition. We call this graph ...
3
votes
3answers
39 views

Proof on Graph Theory.

If G is a connected planar graph, then G has a vertex of degree at most 5. Any planar graph can be colored with 5/6 colors. Any tree has atleast one leaf. Solutions: Although I've read a lot on ...
3
votes
2answers
27 views

Edges between two parts of graph

Consider a (simple undirected) graph $G$ with set of vertices $V=A\cup B$ with $|B|=30$. (1) Every vertex in $A$ has an edge to exactly $3$ vertices in $B$. (2) Every vertex in $B$ has an edge to ...
1
vote
2answers
15 views

Can a K1 graph be a maximal clique of a graph?

I had a discussion with my teacher, whether $K_1$, the complete graph on a single vertex, can be a maximal clique of a given graph. I was notified that it couldn't be a maximal clique, because $K_1$ ...
1
vote
1answer
16 views

How does $\mathcal{A}\cup \mathcal{B}$ indicates that there is at least one augmenting path on $\mathcal{A}$?

I had an exam and there was the following question: $\mathcal{A}$ and $\mathcal{B}$ are matchings in a graph $G$, with $|\mathcal{A}|< |\mathcal{B}|$, study the graph formed with the edges of ...
1
vote
1answer
19 views

Example showing ,for a given graph G , spanning trees need not be unique

The following question appeared in my examination : Give an example to show that for a given graph G , spanning trees need not be unique . but I was unable to construct an example for this ...
4
votes
0answers
37 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
8
votes
3answers
65 views

How many “good” graphs of size $n$ are there?

Let's a call a directed simple graph $G$ on $n$ labelled vertices good if every vertex has outdegree 1 and, when considered as if it were undirected, it is connected. How many good graphs of size $n$ ...
0
votes
0answers
21 views

unique cycles in strongly connected labeled digraphs.

Define a "characterizing cycle" as a cycle in a labeled digraph, along with a distinguished node, such that the sequence of labels starting from that node is unique to that cycle and node. Note: the ...
0
votes
1answer
27 views

Minimal cuts in network.

Let $(S_1, \overline{S_1} ) , (S_2, \overline{S_2} )$ be minimum cuts in some network. Thesis: The $(S_1 \cap S_2, \overline{S_1 \cap S_2)}$ is minimum cuts in this network. Thesis is true? Why? I ...
0
votes
1answer
33 views

Is it possible to apply properties of nodes in a graph to its edges?

I have a graph whose vertices represent points in geometric space. The edges of this graph represent line segments between various points. Is it possible to assign a direction to an edge based on ...
2
votes
0answers
33 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
3
votes
1answer
21 views

How many subgraphs of $K_{m,n}$ are there that contain m + n vertices?

In this problem, a subgraph of $G = (V,E)$ is given by $G' = (V', E')$ where $V' \subset V$ and $E'$ is subset of edges of $E$ that connect two vertices in $V'$. How many subgraphs of $K_{m,n}$ are ...
1
vote
1answer
33 views

Counting the number of unicyclic graphs

Could you help me giving me the number of unicyclic graphs with k vertices and k edges ? I remind that a unicyclic graph with k vertices and k edges is a tree with k vertices and k-1 edges to wich we ...
1
vote
1answer
20 views

Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more ...
0
votes
1answer
28 views

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$. $M$*$(K_5)$ is the dual matroid representing the graph $K_5$, that is, a complete graph with 5 vertices. How do I solve this? ...
5
votes
1answer
46 views

Special case of Minimum Spanning Tree

I have been bashing my head trying to solve the following problem for the past two days, it is a review question in preparation for my exam and I assume something similar will be on it. The problem ...
-3
votes
0answers
38 views

What is the chromatic number of $G_1 \cup G_2$? [on hold]

Please give me some advice. Let $G=G_1 \cup G_2$ where $V_1 \cap V_2 = \emptyset$. Prove that: $$\chi(G) \le \chi(G_1)\chi(G_2).$$
0
votes
1answer
28 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...
0
votes
1answer
53 views

Marriage theorem. Proof. [on hold]

I am asking for advice: Let G be the bipartite graph $(V_1, E, V_2)$ with each vertex in $V$, of degree at least $d (> 0)$ and each vertex in $V_2$ of degree $d$ or less. Show that if each vertex ...
0
votes
1answer
43 views

How can a bipartite simple graph be non isomorphic

From my understanding the bipartite graph is a graph that follows the red blue color scheme. If the graph fails the red blue color, then the graph is not bipartite. But the question how do you test a ...
1
vote
1answer
22 views

Removal of cut edge disconnects this graph

I am not sure how does removing cut edge {a,b} disconnects the graph. My interpretation of disconnect means when the graph has multiple components. Original graph before removal graph after ...
3
votes
1answer
42 views

A consequence of the fan lemma for graphs (a theorem of H. Perfect)

Let $G$ Be a graph, $x$ a vertex of $G$ and $Y$ and $Z$ subsets of $V - \{x\}$ and $|Y| < |Z|$. Suppose there are fans from $x$ to $Y$ and from $x$ to $Z$. I want to show that there exist $z \in ...
3
votes
2answers
51 views

why is the Petersen Graph the smallest hypohamiltonian graph?

I know that the Petersen graph is hypohamiltonian. (Which means it is not hamiltonian, but each vertex-deleted subgraph is.) Why is it the smallest hypohamiltonian graph? (without considering $K_2$ ...
0
votes
0answers
33 views

Nullifying columns of a matrix by nullifying rows

Let $A$ be a real rectangular matrix. Each column of $A$ is a nonzero vector. Now each row of $A$ is nullified with probability $p$, all independently of each other. What is the probability that ...
3
votes
0answers
37 views

Complete bipartite graphs with odd/even edge conditions

Given a simple graph $G$ with $n$ vertices. Prove that there exist simple graphs $S_1,\ldots,S_k$ with $k\leq\frac34n$, such that every $S_i$ is a complete bipartite graph, every edge of $G$ is ...
1
vote
1answer
16 views

show that a loopless graph $G$ contains a bipartite spanning subgraph $H$ such that $d_H(v) \ge \frac{1}{2} d_G(v)$ for all v $\in$ V.

The hint in the appendix of book says that bipartite subgraph with with largest possible number of edges has such a property, but I don't know how to use this hint! any help would be appreciated.
1
vote
2answers
27 views

graph theory “ three nodes of degree 0 1 3 respectively”

Does this graph exist " 3 nodes of degree 0 1 3 respectively" i don't think so because if you have a degree of zero it would be disconnected from the other 2 nodes and on that premise you cannot ...
0
votes
0answers
41 views

Number of ways to connect N nodes with K edges.

Given a graph with N nodes, I have to find the number of different ways the nodes can be connected with the K edges such as the resulting graph is connected. For N = 3 and K = 2, the possibilities ...
2
votes
1answer
33 views

Showing non existence of topological minors in a graph

Recall that a subgraph $H$ of $G$ is called a topological minor if by only adding vertices, edges to $H$ and subdividing some edges of $H$ one can construct $G$. For small graphs, it is easy to show ...
0
votes
3answers
29 views

Proof n-cube graph is connected

I am studying graph theory and my text book gives a proof for an n-cube graph being connected that I find really weird/confusing. Is there a simpler proof to show that the n-cube is connected. The ...
1
vote
0answers
19 views

concerning Graph Theory/subgraphs/ even degree [duplicate]

Given a simple Graph $G=(V,E)$ ($V$ vertices, $E$ edges) I have to show that there exists a distribution $V= V_1 \cup V_2$ of the vertices such that all vertices in the induced subgraphs $G[V_1]$ and ...
1
vote
1answer
41 views

Given n vertices, how many unique graphs can be drawn with k edges?

I am not a mathematician. I've been working on a problem for some time, and I can't seem to be able to grasp the solution. I need to find an algorithmic way to solve for the number of connected, ...
2
votes
2answers
32 views

Given a simple connected bipartite graph $G$ with degree of vertices equal to $k$, where $k\ge 2$. Prove that there is no cut vertex exist in $G$.

Given a simple connected bipartite graph $G$ with degree of vertices equal to $k$, where $k\ge 2$. Prove that there is no cut vertex exist in $G$. Cut vertex $v$ here is a vertex which make the ...
0
votes
0answers
28 views

How can I show that G is bipartite with not adjacent vertices in subgraph? [on hold]

I shall show that an undirected graph G is bipartite , if each subgraph K of G has got a set X subset of V(K) with pairwise not adjacent vertices with 2*|X| ≥|V(K)| . Sorry, is this better ? So, I ...
0
votes
1answer
22 views

$2$-connected and maximum cycles [on hold]

Let $G$ be $2$-connected simple graph. How can I prove that if $C$ and $D$ are the cycles of maximum length in $G$ , then they share at least $2$ vertices..
1
vote
1answer
24 views

calculating a chromatic polynomial

I am going through some questions in the "Bondy,Murty - Graph Theory with applications" book, and I have stumbled upon the following question: calculate the Chromatic Polynomial of the following ...
-1
votes
1answer
93 views

Digraph with no source vertex [on hold]

Show that in every digraph in which there is no source vertex there are two vertices with the same in-degree. I have tried to derive it using the definition and the properties, but I still can't ...
1
vote
0answers
59 views

Induced cycle of odd length in a large graph

I'm trying to prove the following result in order to solve a different problem but I'm stuck; however I'm not sure if it is true, so I'll pose it as a question; Suppose we have a triangle-free ...
1
vote
1answer
27 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
1
vote
2answers
22 views

Number of connected components in a graph with n vertices and n-k edges

Suppose that we have a graph G with n vertices and n-k edges, such that it does not include any cycles. How many components does it have? I am coming up with k components but am having a hard time ...
0
votes
1answer
19 views

Triangular inequality in weighted graphs

In a finite directed complete graph $G ( V, E )$, if all edges have weight either $1$ or $2$, how to show that weights of edges of $G$ satisfies "Triangular Inequality"? Edited Where triangular ...
0
votes
1answer
23 views

Brook's theorem. Where I make a mistake?

please explain me one thing: According to Brook's theorem $ \chi(G ) \le \deg(u) $ But it can't be true. After all, there are $\deg(u) + 1 $ colors and I'm enclosing a draw. ...
0
votes
1answer
21 views

How many trees can be drawn using$n$ vertices without rebuilding isomorphs?

I'm told to draw all possible trees with exactly $6$ vertices. I was able to draw a maximum of $6$ trees. Any more were isomorphs of these $6$ trees. How can I determine if I have drawn all the trees? ...
4
votes
1answer
92 views

A partition of vertices of a graph

I've got an example for this question, but there are many different possibilites and I don't know how to show this for all graphs. Has got anyone any advice how to begin ? Let $G=(V,E)$ be an ...
0
votes
0answers
32 views

Is the 1-string intonation system graph planr? [closed]

A 1-string intonation system consists of a 1-string, 12-fret guitar. We are given then 3 dysjunct 12-tone sets that have in common the same fundamental and at most a single common endpoint defined ...
0
votes
2answers
30 views

Can anyone give an example for this theorem related to planar graphs?

Theorem: Let $G$ be a connected planar graph with $p$ vertices and $q$ edges, where $p\geq 3$. Then $q\leq3p-6$. Proof: Let $r$ be the number of regions in a planar representation of $G$. By ...
5
votes
2answers
66 views

Vertex-transitive graphs and deletion of vertices

Consider the following graph property: for each $u, v \in V(G)$, we have that $G - u \cong G-v$. This property implies a high "symmetry" of the graph. We can easily see that every vertex-transitive ...
2
votes
1answer
25 views

Number of spanning trees in $K_9$ with the degree of vertex $1$ being $4$

I believe I've gotten this problem, but I'm not sure whether I'm correct, because my familiarity with Prufer codes is very weak. I would appreciate any corrections / comments on the mistakes I've ...